Por algún motivo he estado leyendo unas cuantas cosas sobre generación de números aleatorios (la última vez en Aleatoriedad y seguridad) que no soy capaz de agrupar en menos entradas, así que vuelve a salir como tema recurrente.

En How do you know if an RNG is working? justamente hablan de ese tema(afortunadamente con un enfoque diferente): ¿podemos confiar en nuestro generador de números aleatorios? Siempre se habla de que hay que medir la entropía pero no es algo que sea fácil de realizar ni que todo el mundo esté dispuesto a hacer.

If you look at the literature on random number generators, you’ll find a lot of references to statistical randomness testing suites like Diehard or NIST’s SP 800-22. The gist of these systems is that they look a the output of an RNG and run tests to determine whether the output is, from a statistical perspective, “good enough” for government work (very literally, in the case of the NIST suite.)

Luego pasa a analizar las cosas que pueden ir mal (la propia inclusión de código para evaluar un generador podría introducir sus propios problemas, por ejemplo). ¿La conclusión?

Solving this problem, at least in software, so we can ensure that code is correct and does not contain hidden ‘easter eggs’, represents one of the more significant research challenges facing those of us who depend on secure cryptographic primitives. I do hope some enterprising graduate students will give these issues the attention they deserve.

Que sería otro aviso de: no tratéis de hacerlo solos y en casa. O algo así.

Una entrada muy chula en Traveling Salesman Problem donde se mezcla un problema clásico, el viajante de comercio (Traveling Salesman Problem) y algo de actualidad, como son los coches con batería, que hay que recargar.

El problema del viajante de comercio es un viejo conocido: dada una lista de ciudades y sus distancias encontrar el recorrido más corto que pase por todas ellas y vuelva a la de inicio TSP en Wikipedia. Es uno de los problemas conocidos como NP difíciles (o NP-duros).

La formulación de esta entrada habla de los puntos de recarga de las baterías del Tesla y ese hipotético recorrido entre ellas, con código, mapas y todo para poder jugar con él. Muy chulo.

En Improving math performance in glibc pudimos leer hace algún tiempo una entrada precisamente sobre eso: mejorar las prestaciones de la biblioteca matemática de glib.

Sobre la forma en que algunas funciones trabajan:

Transcendental functions in glibc are implemented as multiple phases. The first phases of computation use a lookup table of pre-computed values and a polynomial approximation, a combination of which gives an accurate result for a majority of inputs. If it is found that the lookup table may not give an accurate result the next, slower phase is employed. This phase uses a multiple precision representation to compute results to precisions of up to 768 bits before rounding the result to double. As expected, this kills performance; the slowest path for pow for example is a few thousand times slower than the table lookup phase.

Esto es, primero buscan algunos valores precalculados en una tabla y si no se tiene el restultado, se calculan de alguna forma.

Sobre la implementación de números grandes:

The multiple precision number is implemented in glibc as a structure with an integral exponent and an array of numbers for the mantissa.

…

The exponent e can be any integer value and the array d represents the mantissa. Each number in d is a non-negative integer less than 224. Only 32 of the 40 digits are used (the rest being there for additional precision for rounding), giving a maximum precision of 768 bits. The first question one may have is why the mantissa digits are double and not int if their values are going to be only integral.

Y luego ya se mete en detalles más próximos a las operaciones, por ejemplo con la multiplicación y su efecto en el cálculo de potencias:

As much as 97% of the time in computation of pow is spent in the multiplication function! So it is obvious that the first place to look at to get improvements is the multiplication routine.

Lectura interesante.

No es tan frecuente encontrar textos explicando cosas de las que nos gusta comentar aquí. Por eso me gustó leer Cómo se usa la aleatoriedad en la seguridad que es un tema del que hablamos de vez en cuando por aquí (etiqueta random.

Se muestran algunos ejemplos negativos, como el bug de Debian que me suena que habíamos comentado (pero no lo encuentro) y algunos más. También los sistemas de obtención de números aleatorios en sistemas Linux (/dev/random y /dev/urandom).

Por completar, hace tiempo hablábamos de Números aleatorios y seguridad.

En Why passwords should not be stored on a mobile device unas cuantas razones para evitar esa práctica de almacenar contraseñas que se utilizan para conectarse a diversos servicios en nuestro dispositivo móvil.

This often raises the question how to store the username and the password on the device securely. The easy answer to this is: unfortunately not possible.

La solución pasaría por utilizar protocolos de autentificación modernos en los que el dispositivo no almacena una contraseña, sino un token que le identifica y que la concede permisos para determinadas actividades:

The question for an app developer now is: How can you make sure that the customers can use the app with all features without storing the password on the device? The solution: a token-based approach like OAuth 2.0 [4].

La clave está en la limitación para realizar sólo determinadas actividades (para otras se le pediría la contraseña en el momento) de forma que no está almacenada, no tiene que teclearla en cada ocasión que necesita hacer algo y el acceso a las partes más valiosas (pero menos frecuentemente utilizadas) sigue protegido con la contraseña.

Podemos recordar aquí que ya hemos hablado algunas veces de OAuth. En OAUTH y seguridad y allí enlazábamos a algunos programitas que lo utilizan.