Mensajes

[¿Que es un RNG?]

Un poco de Background antes de empezar.

¿Que es un RNG?

Segun Wikipedia[1]: Random Number Generation, es el proceso de crear una secuencia de numeros o simbolos que no deben de ser predecibles.

Importancia de numeros Aleatorios

Para entender la importancia de los numeros aleatorios tenemos que preguntarnos ¿Donde utilizamos numeros Aleatorios?

Segun Schneier B. (2000)  Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator recuperado de [2]

Los numeros Aleatorios en Criptografia son usados por

• Sesiones y llaves de mensajes para algoritmos de cifrado simetrico como tripe-Des Blowsh
• Como semillas para rutinas que generan valores matematicos como numeros primos muy grandes para RSA
• Saltos de password para frustrar ataques por fuerza bruta fuera de linea
• Vectores de Inicializacion (IV) para bloques de algoritmos de cidrado (AES CBC, ECB etc)
• Valores Aleatorios para Firmas Digitales de Cifrado como  DSA
• Desafios Aleatorios en protocolos de Autenticacion como Kerberos
• "Nonces" para protocolos y garantizar que cada ejecucion es unicia SSL

Me tome la molestia de traducir y agregar toda la lista para ejemplificar que el uso de numeros aleatorios es muy basto y mas comun de lo que piensan, cada que entran a una pagina web con SSL activado se generan numeros aleatorios.

Ahora ya con este Background sobre los RNG y el uso de numeros aleatorios en cryptogradia es posible  entrar en el Tema del Post

¿Que es el "Intel Secure Key RNG"?

Si bien por el nombre podriamos pensar que alguna especie de Llave USB o alguna pienza sofisticada de Hardware, pues estamos en un error!!
El mencionado Intel Secure Key RNG no es nada mas que una Instruccion nueva para procesadores modernos de Intel la cual nos devuelve valores aleatorios Generados directamente por el procesador [3]

Esto es Genial ya que en teoria le quita la Carga al Sistema Operativo de Generar Numeros Aleatorios utilizando algoritmos pesados
¿O no?

Pues bien dada la desconfianza que existe hacia cualquier implentacion del tipo privado, debido a debilidades y/o backdoors documentados. Los sistemas operativos modernos no toman estos "sources" de numeros aleatorios para servirlos directamente a las aplicaciones que soliciten numeros aleatorios, sino que los pasan atraves de algun algoritmo adicional y finalmente sirven sus propios numeros generados.

Esto lo hacen con el objetivo de elimiar cualquier rastro de backdoor que pueda existir.

La instruccion rdrand es usada por sistemas como Linux[4] y FreeBSD[5]  entre otros para  sus plataformas de Intel. Y como se menciono no la usan como valor directo, si no como uno de tantos origenes de Entropia para sus algoritmos de /dev/random

Personalmente he trabajado con el Kernel de FreeBSD y he visto en el codigo[6] el uso de la instruccion rdrand.

Entonces que formas tenemos para analizar si la salida directa de rdrand es segura.

Repasemos las caracteristicas que debe tener un RNG, segun [3]

• Cada valor nuevo debe de ser estadisticamente independiente del anterior
• La distribucion de todos los numeros generados debe de ser Uniforme
• La secuencia debe de ser impredecible

Entonces para la comparacion usare varias muestras de 1MB del Disposivo random estandar del sistema, Para este ejemplo /dev/random de FreeBSD 11.1 RELEASE contra varias muestras de 1MB de la salida devuelta directamente por rdrand.

Para hacer esto lo mas amigable posible desarrolle un modulo para el kernel de FreeBSD [7] que al igual que /dev/random, nos genera un device /dev/rdrand que nos devuelve un stream de numeros aleartorios pero en esta ocacion tomados directamente de la instruccion rdrand para procesadores Ivy Bridge.

Codigo para generar un archivo de muestra:

Código [Seleccionar] Expandir


dd if=/dev/random of=~/random.test count=1 bs=1M
dd if=/dev/rdrand of=~/rdrand.test count=1 bs=1M


Asi mismo desarrolle un programa que lee un archivo y cuenta el numero de veces que aparece cada valor en dicho archivo:


Salida del primer archivo

Código [Seleccionar] Expandir

Abriendo ./random.test
Valor 0: 4161
Valor 1: 4307
Valor 2: 3964
Valor 3: 4124
Valor 4: 4076
Valor 5: 4032
Valor 6: 4031
Valor 7: 4152
Valor 8: 4146
Valor 9: 4078
Valor 10: 4155
Valor 11: 4121
Valor 12: 4144
Valor 13: 4117
Valor 14: 4180
Valor 15: 3984
Valor 16: 4113
Valor 17: 4188
Valor 18: 4069
Valor 19: 4127
Valor 20: 3980
Valor 21: 4019
Valor 22: 3959
Valor 23: 4067
Valor 24: 4054
Valor 25: 4124
Valor 26: 4123
Valor 27: 4070
Valor 28: 4151
Valor 29: 4178
Valor 30: 4115
Valor 31: 4117
Valor 32: 4119
Valor 33: 4090
Valor 34: 4120
Valor 35: 4126
Valor 36: 4053
Valor 37: 4055
Valor 38: 4084
Valor 39: 4048
Valor 40: 4137
Valor 41: 4125
Valor 42: 4029
Valor 43: 4060
Valor 44: 4077
Valor 45: 4128
Valor 46: 4205
Valor 47: 3959
Valor 48: 4082
Valor 49: 4019
Valor 50: 4034
Valor 51: 4107
Valor 52: 4125
Valor 53: 4112
Valor 54: 4050
Valor 55: 4011
Valor 56: 4087
Valor 57: 4071
Valor 58: 4039
Valor 59: 4095
Valor 60: 4093
Valor 61: 4088
Valor 62: 4091
Valor 63: 4006
Valor 64: 4081
Valor 65: 4047
Valor 66: 4102
Valor 67: 4138
Valor 68: 4106
Valor 69: 4019
Valor 70: 4167
Valor 71: 4118
Valor 72: 4145
Valor 73: 4216
Valor 74: 4129
Valor 75: 4210
Valor 76: 4188
Valor 77: 4079
Valor 78: 4130
Valor 79: 4156
Valor 80: 4129
Valor 81: 4075
Valor 82: 4069
Valor 83: 4097
Valor 84: 4113
Valor 85: 4034
Valor 86: 4107
Valor 87: 3944
Valor 88: 4084
Valor 89: 4310
Valor 90: 4082
Valor 91: 4075
Valor 92: 4110
Valor 93: 4113
Valor 94: 4063
Valor 95: 4133
Valor 96: 4207
Valor 97: 4031
Valor 98: 4166
Valor 99: 4009
Valor 100: 4249
Valor 101: 4076
Valor 102: 4155
Valor 103: 4051
Valor 104: 4052
Valor 105: 4115
Valor 106: 4157
Valor 107: 4013
Valor 108: 4093
Valor 109: 4076
Valor 110: 4126
Valor 111: 4156
Valor 112: 4099
Valor 113: 4079
Valor 114: 4049
Valor 115: 4125
Valor 116: 4018
Valor 117: 3990
Valor 118: 4014
Valor 119: 4114
Valor 120: 4058
Valor 121: 4086
Valor 122: 4016
Valor 123: 4034
Valor 124: 3991
Valor 125: 4044
Valor 126: 4224
Valor 127: 4047
Valor 128: 4189
Valor 129: 4160
Valor 130: 4056
Valor 131: 4073
Valor 132: 4009
Valor 133: 4154
Valor 134: 4163
Valor 135: 4130
Valor 136: 4108
Valor 137: 4226
Valor 138: 4099
Valor 139: 4198
Valor 140: 4004
Valor 141: 4037
Valor 142: 4139
Valor 143: 4129
Valor 144: 4085
Valor 145: 4211
Valor 146: 4036
Valor 147: 4010
Valor 148: 4136
Valor 149: 4167
Valor 150: 4135
Valor 151: 4100
Valor 152: 4061
Valor 153: 4115
Valor 154: 4022
Valor 155: 4074
Valor 156: 4164
Valor 157: 3978
Valor 158: 3999
Valor 159: 4041
Valor 160: 4094
Valor 161: 4003
Valor 162: 4008
Valor 163: 4063
Valor 164: 4200
Valor 165: 4202
Valor 166: 4192
Valor 167: 3978
Valor 168: 4120
Valor 169: 4133
Valor 170: 4204
Valor 171: 4176
Valor 172: 4100
Valor 173: 4092
Valor 174: 4109
Valor 175: 4071
Valor 176: 4091
Valor 177: 4067
Valor 178: 4044
Valor 179: 4070
Valor 180: 4024
Valor 181: 4012
Valor 182: 4130
Valor 183: 4062
Valor 184: 4096
Valor 185: 4092
Valor 186: 4110
Valor 187: 4031
Valor 188: 3931
Valor 189: 4065
Valor 190: 4156
Valor 191: 4167
Valor 192: 4033
Valor 193: 4176
Valor 194: 4000
Valor 195: 4174
Valor 196: 4054
Valor 197: 4126
Valor 198: 4121
Valor 199: 4089
Valor 200: 4154
Valor 201: 4192
Valor 202: 4087
Valor 203: 4164
Valor 204: 4176
Valor 205: 4134
Valor 206: 4082
Valor 207: 4103
Valor 208: 4234
Valor 209: 4022
Valor 210: 3978
Valor 211: 4188
Valor 212: 4104
Valor 213: 4168
Valor 214: 4005
Valor 215: 4065
Valor 216: 4118
Valor 217: 4102
Valor 218: 4108
Valor 219: 4077
Valor 220: 4094
Valor 221: 3951
Valor 222: 4078
Valor 223: 4005
Valor 224: 4012
Valor 225: 4131
Valor 226: 4190
Valor 227: 4058
Valor 228: 4036
Valor 229: 4111
Valor 230: 4137
Valor 231: 4000
Valor 232: 4175
Valor 233: 4164
Valor 234: 4253
Valor 235: 4067
Valor 236: 4081
Valor 237: 4037
Valor 238: 4116
Valor 239: 4155
Valor 240: 4137
Valor 241: 4025
Valor 242: 4052
Valor 243: 4140
Valor 244: 4132
Valor 245: 4115
Valor 246: 4063
Valor 247: 3924
Valor 248: 4174
Valor 249: 4098
Valor 250: 4115
Valor 251: 4105
Valor 252: 4083
Valor 253: 4138
Valor 254: 4152
Valor 255: 4098


Salida del segundo archivo

Código [Seleccionar] Expandir

Abriendo ./rdrand.test
Valor 0: 4043
Valor 1: 4055
Valor 2: 4191
Valor 3: 4058
Valor 4: 4125
Valor 5: 4087
Valor 6: 4090
Valor 7: 4150
Valor 8: 4007
Valor 9: 4139
Valor 10: 4027
Valor 11: 4054
Valor 12: 4059
Valor 13: 4167
Valor 14: 4024
Valor 15: 4115
Valor 16: 4045
Valor 17: 4135
Valor 18: 4007
Valor 19: 3980
Valor 20: 4169
Valor 21: 4131
Valor 22: 3997
Valor 23: 4051
Valor 24: 4223
Valor 25: 4110
Valor 26: 4185
Valor 27: 4109
Valor 28: 4052
Valor 29: 4093
Valor 30: 4108
Valor 31: 4163
Valor 32: 4119
Valor 33: 4129
Valor 34: 4180
Valor 35: 4061
Valor 36: 4010
Valor 37: 4082
Valor 38: 4104
Valor 39: 4116
Valor 40: 4080
Valor 41: 4191
Valor 42: 4061
Valor 43: 4103
Valor 44: 4249
Valor 45: 4165
Valor 46: 4043
Valor 47: 4187
Valor 48: 4121
Valor 49: 4141
Valor 50: 4113
Valor 51: 4093
Valor 52: 4177
Valor 53: 3970
Valor 54: 4195
Valor 55: 4156
Valor 56: 4065
Valor 57: 4171
Valor 58: 4113
Valor 59: 4041
Valor 60: 4128
Valor 61: 4189
Valor 62: 4067
Valor 63: 4102
Valor 64: 4063
Valor 65: 4143
Valor 66: 4041
Valor 67: 4029
Valor 68: 4085
Valor 69: 4074
Valor 70: 4053
Valor 71: 4160
Valor 72: 4130
Valor 73: 4179
Valor 74: 4154
Valor 75: 4060
Valor 76: 4073
Valor 77: 4086
Valor 78: 4137
Valor 79: 4107
Valor 80: 4053
Valor 81: 4172
Valor 82: 4120
Valor 83: 4072
Valor 84: 3953
Valor 85: 4116
Valor 86: 4042
Valor 87: 4218
Valor 88: 4082
Valor 89: 3955
Valor 90: 4034
Valor 91: 4055
Valor 92: 4120
Valor 93: 4102
Valor 94: 3953
Valor 95: 4098
Valor 96: 4004
Valor 97: 3993
Valor 98: 4163
Valor 99: 3977
Valor 100: 4118
Valor 101: 4233
Valor 102: 4081
Valor 103: 4158
Valor 104: 4067
Valor 105: 4046
Valor 106: 4099
Valor 107: 4102
Valor 108: 4096
Valor 109: 4117
Valor 110: 4046
Valor 111: 4060
Valor 112: 4114
Valor 113: 4015
Valor 114: 4090
Valor 115: 4040
Valor 116: 4160
Valor 117: 4126
Valor 118: 4119
Valor 119: 4129
Valor 120: 4075
Valor 121: 4026
Valor 122: 4000
Valor 123: 4088
Valor 124: 4144
Valor 125: 4182
Valor 126: 4119
Valor 127: 4076
Valor 128: 4068
Valor 129: 4142
Valor 130: 4042
Valor 131: 4038
Valor 132: 4110
Valor 133: 4125
Valor 134: 3985
Valor 135: 4216
Valor 136: 4018
Valor 137: 4113
Valor 138: 4046
Valor 139: 4149
Valor 140: 4063
Valor 141: 4050
Valor 142: 4132
Valor 143: 4108
Valor 144: 4036
Valor 145: 4028
Valor 146: 4153
Valor 147: 4179
Valor 148: 4139
Valor 149: 4072
Valor 150: 4168
Valor 151: 4009
Valor 152: 4095
Valor 153: 4115
Valor 154: 4041
Valor 155: 3954
Valor 156: 4092
Valor 157: 4093
Valor 158: 4035
Valor 159: 4096
Valor 160: 4033
Valor 161: 4133
Valor 162: 3989
Valor 163: 4203
Valor 164: 4048
Valor 165: 4152
Valor 166: 4103
Valor 167: 4195
Valor 168: 4105
Valor 169: 4082
Valor 170: 4046
Valor 171: 4018
Valor 172: 4267
Valor 173: 4201
Valor 174: 4209
Valor 175: 4100
Valor 176: 4009
Valor 177: 3983
Valor 178: 4135
Valor 179: 4168
Valor 180: 4068
Valor 181: 4044
Valor 182: 4013
Valor 183: 3994
Valor 184: 4071
Valor 185: 4062
Valor 186: 4152
Valor 187: 4044
Valor 188: 4078
Valor 189: 4141
Valor 190: 4033
Valor 191: 4133
Valor 192: 4064
Valor 193: 4158
Valor 194: 3962
Valor 195: 4145
Valor 196: 4119
Valor 197: 4040
Valor 198: 3981
Valor 199: 4173
Valor 200: 4025
Valor 201: 4090
Valor 202: 4067
Valor 203: 4049
Valor 204: 4106
Valor 205: 4232
Valor 206: 3987
Valor 207: 4053
Valor 208: 4121
Valor 209: 4177
Valor 210: 4214
Valor 211: 4053
Valor 212: 4095
Valor 213: 4127
Valor 214: 4082
Valor 215: 4109
Valor 216: 4107
Valor 217: 4181
Valor 218: 4224
Valor 219: 4142
Valor 220: 4112
Valor 221: 4165
Valor 222: 4121
Valor 223: 4088
Valor 224: 4073
Valor 225: 3984
Valor 226: 4112
Valor 227: 4054
Valor 228: 4151
Valor 229: 4120
Valor 230: 4040
Valor 231: 4129
Valor 232: 4099
Valor 233: 4085
Valor 234: 4078
Valor 235: 4149
Valor 236: 4101
Valor 237: 3985
Valor 238: 3999
Valor 239: 4085
Valor 240: 4138
Valor 241: 4300
Valor 242: 4078
Valor 243: 4265
Valor 244: 4194
Valor 245: 4027
Valor 246: 4130
Valor 247: 4225
Valor 248: 4111
Valor 249: 4102
Valor 250: 4046
Valor 251: 4059
Valor 252: 3974
Valor 253: 4096
Valor 254: 4155
Valor 255: 4089


A simple vista parece que ambas salidas tienen una distribucion uniforme de los valores, con esto comprobamos la segunda propiedad de los RNG "La distribucion de todos los numeros generados debe de ser Uniforme"

Falta validar las otras 2 propiedades pero de momento es suficiente.

¿Entonces podemos decir que el Intel Secure Key RNG es Seguro?

No de momento con las pruebas hechas no hay manera de afirmar que sea seguro o inseguro.

Sin embargo las concluciones mencionadas en[10] comentan que la instroduccion de rdrand en los sistemas mejora y simplifica la generacion de numeros aleatorios ademas recomiendan usarlo junto con otros sources de entropia.



Referencias
[1] https://en.wikipedia.org/wiki/Random_number_generation
[2] https://www.schneier.com/academic/paperfiles/paper-yarrow.pdf
[3] https://software.intel.com/sites/default/files/m/d/4/1/d/8/441_Intel_R__DRNG_Software_Implementation_Guide_final_Aug7.pdf
[4] https://www.theregister.co.uk/2013/09/10/torvalds_on_rrrand_nsa_gchq/
[5] https://arstechnica.com/information-technology/2013/12/we-cannot-trust-intel-and-vias-chip-based-crypto-freebsd-developers-say/
[6] https://svnweb.freebsd.org/base/release/11.1.0/sys/dev/random/ivy.c?view=markup
[7] https://github.com/albertobsd/rdrand
[8] https://eprint.iacr.org/2014/504.pdf
[9] http://spectrum.ieee.org/computing/hardware/behind-intels-new-randomnumber-generator
[10] http://www.electronicdesign.com/learning-resources/understanding-intels-ivy-bridge-random-number-generator

Mejor busca uno de pago, tienen mas soporte, estabilidad y ademas no cuestan mucho.

Saludos!

Pasa seguido que algunos switches se traben o hagan cosas raras, ya se por problemas de administracion de memoria del firmware o algun otro problema similar.

Lo ideal seria buscar una version del firmware mas actualizada.

Saludos!

Que por cierto yo como padre estaria mas preocupado por que mi hijo este haciendo algo ilegal (Meterse a la Wifi del Vecino es Ilegal). Minimo le diria que cambie la MacAddress o algo similar

Y si, como ya dijieron, lo raro seria que no vea esas paginas. Es normal.

Saludos!

se decidió no usar internet por 2 meses, pidieron pues a la proveedora que nos lo desactive por ese tiempo

Tienen el equipo Router/modem todavia en el domicilio?

Es raro que eso suceda, sigue investigando, no des por descartado nada.

Realmente si no tienen internet es imposible que eso suceda, sin embargo yo mismo he visto que los ISP son muy malos bloqueando las conexiones. Posiblemente tenias en la cache DNS de tu ordenador algunas de las IP de los trackers de los torrents por lo cual podias seguir comunicandote con ellos.

Saludos!

[Ejemplo ficticio]

Fuente: https://albertobsd.blogspot.mx/2017/07/cable-modem-ubee-wpa2-y-wps-por-defecto.html




Bueno recientemente me instalaron el internet de Megacable (ISP de Internet y Televicion en Mexico ) y me entregaron un modem algo desconocido, pero realmente desconozco que tan usado sea esta marca de modems en las tecnologias de cable coaxial.

Me instalaron un  cable modem Ubee Modelo 1307

desconozco si estas condifuraciones sean para todos lo modelos he incluso para este mismo modelo en otra Compañia de cable.

La cable WPA/WPA2 por defecto para el equipo que me entregaron es PARTE de la MAC Address ORIGINAL. En especifico los ultimos 5 Octetos

Resalto "parte" y "original" ya que si escaneamos las redes Wireless la MAC address Wireless cambia en el ultimo octeto.

Ejemplo ficticio

MAC Adress Original: F8:DA:0C:00:00:00 (Esta es la que viene en nuestra etiqueta)
MAC Adress WAN: F8:DA:0C:00:00:01 (Esta es la que reconoce la compañia de cable)
MAC Adress MTA: F8:DA:0C:00:00:02 (NPI)
MAC Adress Ethernet: F8:DA:0C:00:00:03 (Mac address que ven las computadoras conectas por cable)
MAC Adress Wireless: F8:DA:0C:00:00:04 (Mac addres que ven los equipos wireless)

Entonces para este caso ficticio la cable WPA es DA0C000000
Y el SSID de la red Inalambrica es: Ubee0000

Los datos reales pueden cabiar.

Entonces si tenemos acceso a la MAC address inalambrica la clave serian los 4 octetos de en medio mas los 2 ultimos digitos del SSID.

Otro ejemplo

MAC Adress Wireless: F8:DA:0C:10:10:04
SSID: Ubee1000

La cable WPA seria los numeros resaltados a continuacion:
MAC Adress Wireless: F8:DA:0C:10:10:04
SSID: Ubee1000

Por lo que para este ejemplo seria DA0C101000

Ademas de todo esto el PIN WPS por default que venia en mi dispositivo es 12345670

Interfaz Web

La direccion para acceder a la interfaz web es http://192.168.0.1

El usurio y clave para entrar es user, user esto es:
usuario: user
contraseña: user

Recomendaciones
Desactivar el WPS
Cambiar el nombre de la red inalambrica
Cambiar la clave por defecto.


VULNERABLE A REAVER por defecto.

Atacando mi Equipo con Reaver:

Código [Seleccionar] Expandir

# reaver -b F8:DA:0C:XX:XX:XX  -i mon0 -vv

Reaver v1.4-r119 WiFi Protected Setup Attack Tool
Copyright (c) 2011, Tactical Network Solutions, Craig Heffner <cheffner@tacnetsol.com>


[+] Switching mon0 to channel 10
[+] Waiting for beacon from F8:DA:0C:XX:XX:XX
[+] Associated with F8:DA:0C:XX:XX:XX (ESSID: EyL)
[+] Trying pin 12345670
[+] Sending EAPOL START request
[+] Received identity request
[+] Sending identity response
[+] Received M1 message
[+] Sending M2 message
[+] Received M3 message
[+] Sending M4 message
[+] Received M5 message
[+] Sending M6 message
[+] Received M7 message
[+] Sending WSC NACK
[+] Sending WSC NACK
[+] Pin cracked in 4 seconds
[+] WPS PIN: '12345670'
[+] WPA PSK: 'XXXXXXXXXXXXXX'
[+] AP SSID: 'XXXXXXXXXXXXXX'
[+] Nothing done, nothing to save.


[¿Como puedo incrementar la direccion a la que apunta mi apuntador en 1 bytes?]

Muy buen dia.

Realmente no termine de leer el programa por que no me queda claro que es lo que hace.

Cuando pidas ayuda con este tipo de problemas de apuntadores busca un Ejemplo basico pero que exprese lo que no entiendes.

Ejemplo

¿Como puedo incrementar la direccion a la que apunta mi apuntador en 1 bytes?

Código (c) [Seleccionar] Expandir

#include<stdio.h>

int main() {
char *cadena = "Esta es una direccion de memoria que contiene caracteres ascii";
char *ptr;
ptr = cadena;
*ptr++;
printf("Cadena apunta a %p y ptr apunta a %p",cadena,ptr);
return 0;
}


Salida en mi computadora

Código [Seleccionar] Expandir

Cadena apunta a 0040A064 y ptr apunta a 0040A065

Espero que respondas tu duda nuevamente mejor redactada y con un ejemplo de tup problema y con gusto te ayudamos.

Saludos!

A veces, resolver una ecuación, ofusca mucho el código jaja

A muchas personas no se le dan las matematicas, asi que por si sola una ecuacion podria considerarse ofuscada, ahora una ecuacion plasmada en un lenguaje y con operadores a nivel de bits ni  de diga.

Cabe añadi que la ecuacion que puso ivancea96, lo hace en un solo paso. Yo lo dividi en 2 pasos para sacar el rango de 0 a A y de 0 a B para posteriormente realizar la resta.

Saludos!

Yo si no está ofuscado, no me parece correcto.

Código (cpp) [Seleccionar] Expandir

#include <cstdio>

int getResult(int a, int b){
return (b*b+(b&1)*(b*2+1)-a*a+(a&1)*(a*2-1))>>2;
}


Barbaro y con Operadores de bits!!! Bravo!!

Buenas!

Este problema lo vi en otro Foro, pero me gustaria ampliarlo y Discutir sobre la eficiencia del codigo contra la "FORMA FACIL".


Problema
Tu tienes que proporcionar la Suma de Todos los numeros Impares contenidos en un rango de numeros dados [a,b]

Ejemplo:
a = 5
b = 10
Numeros impares en el rango [5,10] = { 5,7,9 };
Sumatoria 5 +7 + 9 = 21

Ejemplo
a = 1
b = 5
Numeros impares en el rango [1,5] = { 1,3,5 };
Sumatoria 1+3 +5 = 9

Entrada del programa:
Pueden existir multiples casos para probar, La primera Linea contiene el valor T Donde T es el numero de casos a realizar,  1 <= T  <= 100000
Y seguido de T Casos, Cada Caso consiste en dos Numeros enteros a, b  donde 0 <= a <=b <=10000. En dos lineas sepaadas (1 linea por numero entero)

Ejemplo de Entrada:

Código [Seleccionar] Expandir

2
5
10
1
5

Ejemplo de salida

Código [Seleccionar] Expandir

Caso 1: 21
Caso 2: 8




La solucion que muchos aplican es codigo:

Código (c) [Seleccionar] Expandir


int T= 0,a = 0,b= 0,i,suma;
scanf("%d\n",&T);
i = 0;
while(i < T) {
scanf("%d\n",&a);
scanf("%d\n",&b);
suma = 0;
while(a <= b) {
if(a % 2 == 1) {
suma += a;
}
a++;
}
printf("Case %i:%i\n",i+1,suma);
i++;
}


Sin embargo en mi punto de vista es bastante ineficiente, ya que si te dan 10000 Veces el peor de los casos de [0,10000] (Pongo 10000 y no 100000 para que no desborde el entero de 32 bits...) En dado caso tu programa ejecutaria un ciclo de 10000 * 10000 = 100'000,000
Claro que para los procesadores modernos no hay tanta direrencia entre 100, Mi aproximacion fue sacar la formula para determinar la sumaria de los impares del rango de 0 a A y del rango de 0 a B

Y En teoria solo entro al ciclo T veces:

Código (c) [Seleccionar] Expandir


#include<stdio.h>

int main() {
int T= 0,a = 0,b= 0,i;
int rango_a,rango_b;
scanf("%d\n",&T);
i = 0;
while(i < T) {
scanf("%d\n",&a);
scanf("%d\n",&b);
if(a % 2 != 0) {
a-=1;
}
rango_a = (((a/2)*a)/2); // Suma de Impares desde 0 hasta a-1
if(b % 2 == 0) {
rango_b = (((b/2)*b)/2); //Suma de Impares desde 0 hasta b
}
else {
rango_b = ((((b+1)/2)*(b+1))/2); //Suma de Impares desde 0 hasta b
}
printf("Case %i:%i\n",i+1,rango_b-rango_a);
i++;
}
return 0;
}




Consideren el siguiente archivo de Entrada 10000 veces rangos de [0,10000]
http://pastebin.com/raw/nK0xQ6cz