Linus Torvalds y C++

Sorprendente la perla que nos deja Linus en referencia al lenguaje C++. No tiene desperdicio.

Dejo aquí una copia (el enlace aquí)

On Wed, 5 Sep 2007, Dmitry Kakurin wrote:
#
# When I first looked at Git source code two things struck me as odd:
# 1. Pure C as opposed to C++. No idea why. Please don't talk about portability,
# it's BS.

*YOU* are full of bullshit.

C++ is a horrible language. It's made more horrible by the fact that a lot
of substandard programmers use it, to the point where it's much much
easier to generate total and utter crap with it. Quite frankly, even if
the choice of C were to do *nothing* but keep the C++ programmers out,
that in itself would be a huge reason to use C.

In other words: the choice of C is the only sane choice. I know Miles
Bader jokingly said "to piss you off", but it's actually true. I've come
to the conclusion that any programmer that would prefer the project to be
in C++ over C is likely a programmer that I really *would* prefer to piss
off, so that he doesn't come and screw up any project I'm involved with.

C++ leads to really really bad design choices. You invariably start using
the "nice" library features of the language like STL and Boost and other
total and utter crap, that may "help" you program, but causes:

- infinite amounts of pain when they don't work (and anybody who tells me
that STL and especially Boost are stable and portable is just so full
of BS that it's not even funny)

- inefficient abstracted programming models where two years down the road
you notice that some abstraction wasn't very efficient, but now all
your code depends on all the nice object models around it, and you
cannot fix it without rewriting your app.

In other words, the only way to do good, efficient, and system-level and
portable C++ ends up to limit yourself to all the things that are
basically available in C. And limiting your project to C means that people
don't screw that up, and also means that you get a lot of programmers that
do actually understand low-level issues and don't screw things up with any
idiotic "object model" crap.

So I'm sorry, but for something like git, where efficiency was a primary
objective, the "advantages" of C++ is just a huge mistake. The fact that
we also piss off people who cannot see that is just a big additional
advantage.

If you want a VCS that is written in C++, go play with Monotone. Really.
They use a "real database". They use "nice object-oriented libraries".
They use "nice C++ abstractions". And quite frankly, as a result of all
these design decisions that sound so appealing to some CS people, the end
result is a horrible and unmaintainable mess.

But I'm sure you'd like it more than git.





Linus

Criptografía de Curva Elíptica

Las curvas elípticas son ampliamente usadas en criptografía, especialmente en criptografía asimétrica (o de clave pública). Una de sus mayores ventajas es la velocidad que ofrece, debido a que requiere longitudes de clave mucho menores a las de criptosistemas como RSA.

A continuación se introducen las bases de este tipo de criptografía.


Qués son las curvas elípticas?

En criptografía se habla de curva elíptica en referencia a una ecuación y²=x³+Ax+B que cumple 4A³+27B²≠0. Dando diferentes valores a A y B obtenemos todo un conjunto de curvas que, al ser dibujadas, ofrecen una forma similar. Son ejemplos de curvas elípticas y²=x³-x (izquierda) y y²=x³-x+1 (derecha).

Las curvas elípticas tienen ciertas características que las hacen especiales en el mundo de la criptografía. Una de estas características consiste en la posibilidad de poder generar un punto en una curva partiendo de dos puntos dados (o incluso de uno). Este concepto es muy fácil de entender partiendo de la figura siguiente.

Usamos como puntos de partida P y Q, dos puntos conocidos. Trazaremos una linea entre P y Q. Si la linea corta la curva en un tercer punto, lo reflejaremos a través del eje, dando lugar a un nuevo punto R. Esta operación se representa como R=P+Q. En caso de que la linea que pasa por P y Q no corte a la curva en ningún otro punto, diremos que corta la curva en un punto O en el infinito y representaremos esta operación como P+Q=O.

Partiendo de la suma, no es difícil encontrar un mecanismo que nos permita realizar multiplicaciones de tipo kP, siendo k un escalar. Por ejemplo, imaginemos que queremos realizar la operación 13P, es decir, multiplicar 13 por un punto P. Bastaría con realizar la siguiente secuencia de doblado de puntos:

P, 2P=P+P, 4P=2P+2P, 8P=4P+4P, 13P=8P+4P+P

Este simple mecanismo para generar nuevos puntos dota a una curva elíptica de la posibilidad de realizar operaciones aritméticas sobre ella, base de los criptosistemas que estudiaremos en breve.

En criptografía las curvas elípticas se usan sobre campos finitos (Fq) con q muy grande. Un ejemplo de campo finito podría ser F5={0,1,2,3,4}. De manera que el número 7 representado en el campo finito correspondería a 7 mod 5 = 2.
Cuando se usan campos finitos el número de puntos que hay en una curva tambien es finito. Este numero se llama orden de la curva y se representa como #E. Debemos diferenciarlo del orden de un punto, que se refiere al valor k más pequeño (diferente de 0) que multiplicado por P da O.

El problema del logaritmo discreto (DLP)

La criptografía de Clave Pública basa su fuerza en la dificultad de resolver ciertos problemas matemáticos. Uno de los más usados es el problema del logaritmo discreto (Discrete Logarithm Problem - DLP). Este problema se basa en la dificultad que representa resolver una ecuación de tipo x = a^y mod n donde x, a y n son conocidas e y es la variable que se busca. De hecho, para valores de n e y sufientemente grandes es computacionalmente imposible resolver el problema, al menos, con los algoritmos y ordenadores actuales.
El algoritmo más rápido conocido para resolver este problema es el Index Calculus que permite resolverlo en tiempo subexponencial.

El problema del logaritmo discreto en Curvas Elípticas (ECDLP)

Existe una problema similar al problema del logaritmo discreto que puede usarse con Curvas Elípticas. Anteriormente hemos visto como realizar una operación tipo Q=kP de una forma sencilla. Sin embargo, obtener k y P partiendo solo de Q es computacionalmente difícil. De hecho, el algoritmo más rápido que permite encontrar una solución es el algoritmo Rho de Pollard, pero este algorimo es de tiempo exponencial, mucho mas lento que en el caso del ataque a DLP mediante el Index Calculus.
Este hecho es muy importante, pues la dificultad de resolver ECDLP frente a DLP permite que los criptosistemas que se basan en el primero usen claves mucho más cortas. De manera que los sistemas que usan ECDLP requieren mucha menos memoria y capacidad de proceso.
Una clave RSA de 4096 bits ofrece la misma seguridad que una clave de un criptosistema de Curva Elíptica de 313 bits.

Intercambio de Claves de Diffie-Hellman

El intercambio de claves de Diffie-Hellman es un protocolo que permite un intercambio secreto y seguro de claves entre dos partes que no han tenido un contacto previo. Se usa ampliamente en criptografía y se basa en el problema del logaritmo discreto (DLP). Por lo tanto, puede usarse el mismo algoritmo a través del problema ECDLP.

Al algoritmo puede resumirse en los siguientes pasos:

1. Alice y Bob eligen una curva elíptica E sobre un campo finito Fq de manera que el ECDLP sea computacionalmente difícil. También eligen un punto P en dicha curva de manera que su orden sea un número primo grande.

2. Alice elige un entero grande a, calcula PA=aP y envía PA a Bob.

3. Bob elige un entero grande b, calcula PB=bP y envía PB a Alice.

4. Alice calcula aPB=abP

5. Bob calcula bPA=abP


Al finalizar el algoritmo, tanto Alice como Bob disponen de abP. Pero un usario que escuche el canal solo habrá podido obtener PA y PB, los cuales no le permiten calcular abP a menos que resuelva el ECDLP. Alice y Bob solo tendrán que extraer una clave a partir de abP y usarla para enviar datos cifrados. Para tal propósito podrán usar cualquier algoritmo simétrico como DES, AES, etc.

Algoritmo de firma digital (ECDSA)

El algoritmo de firma digital para curvas elípticas está basado en el estandar de firma digital DSA. Este algoritmo ofrece un esquema que permite firmar documentos y verificar las firmas.

Los pasos a seguir para generar claves, firmar y verificar la firma, se muestran a continuación.

Alice genera un par de claves:

1. Alice elige una curva E con orden #E=fr, de manera que r sea un primo grande.

2. Alice busca un punto en la curva de orden r.

3. Alice elige un número aleatorio d situado en el intervalor [2, r-2] y calcula Q=dP.

4. La clave pública corresponde a (E,P,r,Q) y la clave privada a d.



Alice firma un documento M.
(h(M) corresponde al hash de M)

1. Alice elige un número aleatorio k en el intervalo [2, r-2].

2. Se calcula el punto (x, y)=kP

3. R=x mod r

4. s=k¯¹ (h(M) +Rd) mod r, si s es igual cero, empezamos de nuevo.

5. La firma de Alice es (R,s) y se transmite junto con el mensaje M.


Bob verifica la firma de Alice.

1. Bob obtiene la clave pública de Alice.

2. w = s¯¹ mod r

3. u1 = h(M) w mod r

4. u2 = Rw mod r

5. (x, y) = u1P + u2P

6. v = x mod r

7. Si v es igual a R, la firma es válida.


OpenSSL: Un ejemplo práctico de firma digital mediante curvas elípticas.

Des de la versión 0.9.8 la herramienta OpenSSL ofrece algunas opciones para trabajar con curvas elípticas. No están muy documentadas, pero nos servirán para realizar una pequeña demostración del uso de la firma digital.

Para generar un clave ejecutaremos el siguiente comando:

$ openssl ecparam -genkey -name secp224r1 -out key.pem

Ahora tanto la clave pública como la privada se encuentran dentro de key.pem. Podemos extraer la pública con el comando:

$ openssl ec -in key.pem -text -pubout -out pubkey.pem

Ya disponemos de una clave con la que hacer pruebas, por lo que generaremos un mensaje que firmar:

$ echo "El mensaje de prueba de h4ck1t!" > msg.txt

Y lo firmaremos, operación que solo puede realizar el propietario de la clave privada:

$  openssl dgst -sign key.pem -ecdsa-with-SHA1 < msg.txt > msg.sig

Firmado el mensaje, todo usuario que disponga de la clave pública podrá verificar su procedencia:

$ openssl dgst -verify pubkey.pem -ecdsa-with-SHA1 -signature msg.sig < msg.txt
Verified OK

Referencias:

- Elliptic Curves, Number Theory and Cryptography. Lawrence C. Washington. Ed Chapman & HALL/CRC.
- Prime Numbers, a Computational Perspective. Richard Crandall, Carl Pomerance. Ed Springer.
- Criptografía de curva Elíptica, Ataque Rho de Pollard. Daniel Lerch. Hakin9 (6-2007).

Criptoanálisis: Análisis de frecuencias

Análisis de frecuencias:

El análisis de frecuencias es una forma de criptoanálisis utilizada en cifrados de sustitución, basada en el estudio de la frecuencia de aparición de las letras o símbolos de un criptograma. Este análisis se basa en el hecho de que cada lenguaje dispone de una frecuencia característica de aparición de sus letras o grupos de ellas. Por ejemplo, en inglés es común el uso de la letra E mientras que la X raramente aparece. Lo mismo ocurre en los textos en castellano, donde la E y la A son las letras más habituales.

Aproximadamente la distribución de porcentajes de aparición de cada letra en algunas lenguas comunes es la siguiente:

L       Inglés           Francés         Alemán          Castellano

a       8.167%          7.636%          6.51%           12.53%
b       1.492%          0.901%          1.89%           1.42%
c       2.782%          3.260%          3.06%           4.68%
d       4.253%          3.669%          5.08%           5.86%
e       12.702%         14.715%         17.40%          13.68%
f       2.228%          1.066%          1.66%           0.69%
g       2.015%          0.866%          3.01%           1.01%
h       6.094%          0.737%          4.76%           0.70%
i       6.966%          7.529%          7.55%           6.25%
j       0.153%          0.545%          0.27%           0.44%
k       0.772%          0.049%          1.21%           0.00%
l       4.025%          5.456%          3.44%           4.97%
m       2.406%          2.968%          2.53%           3.15%
n       6.749%          7.095%          9.78%           6.71%
o       7.507%          5.378%          2.51%           8.68%
p       1.929%          3.021%          0.79%           2.51%
q       0.095%          1.362%          0.02%           0.88%
r       5.987%          6.553%          7.00%           6.87%
s       6.327%          7.948%          7.27%           7.98%
t       9.056%          7.244%          6.15%           4.63%
u       2.758%          6.311%          4.35%           3.93%
v       0.978%          1.628%          0.67%           0.90%
w       2.360%          0.114%          1.89%           0.02%
x       0.150%          0.387%          0.03%           0.22%
y       1.974%          0.308%          0.04%           0.90%
z       0.074%          0.136%          1.13%           0.52%

A parte de estudiar la frecuencia de aparición de un símbolo, también podemos fijarnos en la frecuencia de aparición de conjuntos de dos, tres, o más letras. En castellano son frecuentes cadenas de dos letras como DE, LA, EL, EN o palabras de tres como QUE, LOS, DEL, LAS y POR.

A continuación se muestran los conjuntos de dos y tres letras más frecuentes:

En Inglés
Conjuntos de dos letras: TH, HE, AN, IN, ER, RE, ES, ON, EA, TI, AT, ST, EN, ND, OR, TO, NT, ED, IS, AR.
Conjuntos de tres letras: THE, ING, AND, ION, ENT, FOR, TIO, ERE, HER, ATE, VER, TER, THA, ATI, HAT, ERS.

En Francés:
Conjuntos de dos letras: ES, EN, OU, DE, NT, TE, ON, SE, AI, IT, LE, ET, ME, ER, EM, OI, UN, QU.
Conjuntos de tres letras: ENT, QUE, ION, LES, AIT, TIO, ANS, ONT, ANT, OUR, AIS, OUS.

En Alemán
Conjuntos de dos letras: EN, ER, CH, DE, GE, EI, IE, IN, NE, ND, BE, EL, TE, UN, ST, DI, NO, UE, SE, AU, RE, HE.
Conjuntos de tres letras: EIN, ICH, DEN, DER, TEN, CHT, SCH, CHE, DIE, UNG, GEN, UND, NEN, DES, BEN, RCH.

En Castellano:
Conjuntos de dos letras: ES, EN, EL, DE, LA, OS, AR, UE, RA, RE, ER, AS, ON, ST, AD, AL, OR, TA, CO.
Conjuntos de tres letras: QUE, EST, ARA, ADO, AQU, DEL, CIO, NTE, OSA, EDE, PER, IST, NEI, RES, SDE.


Al intentar romper un cifrado mediante análisis de frecuencia nuestro objetivo será identificar la frecuencia de aparición de los símbolos usados. Después buscaremos una equivalencia entre estos símbolos y las letras que más aparecen en la lengua usada intentando encontrar un significado. Nos servirán también las frecuencias de aparición de conjuntos de X letras, así como nuestra imaginación a la hora de rellenar huecos al estilo del juego del ahorcado.

En algunos casos puede ser útil conocer el porcentaje de vocales de cada idioma. En inglés, por ejemplo, el porcentaje de vocales es del 40%, igual que en el alemán. Sin embargo, en francés es del 45% y en castellano del 47%. Estos datos, aunque solo son aproximaciones pueden resultar de gran interés en ciertos criptogramas.


Criptoanálisis de ejemplo

Para experimentar con lo comentado anteriormente, imaginemos un sistema de cifrado por sustitución, de manera que cada letra del mensaje ha sido sustituída por un símbolo. El ejemplo de mensaje cifrado es el siguiente:

3# 16_@!5?6#=_# 2> 23 #6!2 |2 2>16_$_6 15% 13#72 >2162!# 5 |2 /% 45|5 2%_?4#!_15

Para iniciar nuestro criptoanálisis, empezaremos realizando un análisis de frecuencias. Para que este proceso no se haga pesado, adjunto un sencillo programa en C++ que lo hará por nosotros.

#include <iostream>
#include <fstream>
#include <algorithm>
#include <map>


int main(int argc, char* argv[])
{
using namespace std;

if(argc!=3)
{
cout << "Usage: " << argv[0] << " [file] [max group size]" << endl;
return 0;
}

for(int i=0; i<atoi(argv[2]); i++)
{
int c;
map<string,int> freq;
ifstream file(argv[1]);
string group;
while( (c=file.get()) && !file.eof() )
{
if(isspace(c))
continue;
group += string(1,c);

if(group.size()>=i+1)
freq[group.substr(group.size()-i-1, i+1)]++;
}

cout << endl << "-- FREQ SIZE " << i+1 << " --" << endl;
int count = 0;
map<string,int>::iterator it = freq.begin();    
for(;it!=freq.end(); it++)
{
if((*it).second>1)
{
count ++;

cout << (*it).first << ": " << (*it).second << "\t";

if(count%6==0)
cout << endl;
}
}
cout << endl;
}
}

Partiendo del programa y del un fichero con el texto cifrado "cipher.txt" realizamos el analisis de frecuencias:

$ g++ freq.cpp
$ ./a.out cipher.txt 3
-- FREQ SIZE 1 --
!: 4    #: 7    %: 3    1: 6    2: 10   3: 3
4: 2    5: 6    6: 6    >: 3    ?: 2    _: 6
|: 3

-- FREQ SIZE 2 --
15: 2   16: 3   2>: 3   3#: 3   5|: 2   6_: 2
>2: 2   |2: 2

-- FREQ SIZE 3 --
16_: 2  2>2: 2

Si observamos el análisis de frecuencias podemos ver que los símbolos que más se repiten son '2' y '#', seguidos de '_', '1', '5' y '6'. Por lo que siguiendo la distribución de porcentajes frecuentes es probable que se correspondan con las letras 'a', 'e', 'i', etc.
Es importante tener en cuenta que esto solo nos da una pista de cuál podría ser el valor de cada símbolo, pero no nos lo dice de forma exacta. Por este motivo será necesario probar varias hipótesis.

Empezaremos suponiendo que '2' corresponde a 'e' y '#' corresponde a 'a'. Si nuestra hipótesis falla, continuaremos probando al revés.
Sustituimo en el texto cifrado:

3A 16_@!5?6A=_A E> E3 A6!E |E E>16_$_6 15% 13A7E >E16E!A 5 |E /% 45|5 E%_?4A!_15

Observando el principio del texto cifrado "3A" y la cuarta palabra "E3" deducimos que '3' corresponde a la letra 'L'. Sustituimos de nuevo.

LA 16_@!5?6A=_A E> EL A6!E |E E>16_$_6 15% 1LA7E >E16E!A 5 |E /% 45|5 E%_?4A!_15

También pueden resultar buenas pistas la tercera palabra "E>" y la sexta "|E". Estas nos indican que ">" podría corresponder a 'S' o 'N', y '|' probablemente corresponderá a 'D'. Vea la frecuencia de grupos de dos letras.
Además, si nos basamos en las suposiciones anterioriores, el grupo '/%' que corresponde a una palabra de dos letras que no contiene ni 'A' ni 'E'. Será pues una de las siguientes: NO, UN, SU, LO, SI, MI, ...

También es una buena pista el '5' solitario, que muy probablemente corresponderá a una 'y' o una 'o'. Pero viendo en la octava palabra '15%' deducimos que dificilmente corresponderá a una 'Y'.

En base a las observaciones anteriores, una buena hipotesis podría corresponder a las siguientes sustituciones: '5' por 'o', '|' por 'D' y '>' por 'S'.

LA 16_@!O?6A=_A ES EL A6!E DE ES16_$_6 1O% 1LA7E SE16E!A O DE /% 4ODO E%_?4A!_1O

Llegados a este punto, más de unos sería capaz de resolver el mensaje utilizando solamente su imaginación. Pero en lugar de dar la solución, vamos a explorar otra técnica interesante. Esta corresponde a atacar las palabras sin descifrar con un diccionario. Como ejemplo usaremos una lista de palabras en castellano que se puede descargar de:

http://lemarios.olea.org/lemario-espanol-2002-10-25.txt.gz

NOTA: Esta lista contiene acentos y ñ, que es recomendable sustituir para poder seguir los siguientes pasos.


Después de descargar y descomprimir la lista de palabras estudiemos que opciones tenemos para acabar de descifrar el mensaje. Una palabra que tiene posibilidades es '1LA7E', una palabra de 5 letras de las cuales conocemos tres. Tambien es interesante atacar la palabra que viene a continuación 'SE16E!A'.

Podemos hacerlo con dos sencillos comandos grep:

$ grep "^.la.e$" lemario-espanol-2002-10-25.txt
alabe
clase
clave
glase
llave
olaje
$ grep "^se..e.a$" lemario-espanol-2002-10-25.txt
secreta
secuela
segueta
septena
serreta

Sin duda, las palabras que buscamos son "CLAVE SECRETA". Así que continuamos con la sustitución:

LA CR_@TO?RA=_A ES EL ARTE DE ESCR_$_R CO% CLAVE SECRETA O DE /% 4ODO E%_?4AT_CO

La última palabra puede confundirnos, pero está claro cuál es la segunda. En cualquier caso:

$ grep "^cr..to.ra..a$" lemario-espanol-2002-10-25.txt
criptografia.
$ grep "^e....at.co$" lemario-espanol-2002-10-25.txt
enigmatico
enzimatico
estomatico

Con lo que la resolución del mensaje es trivial:

"La criptografia es el arte de escribir con clave secreta o de un modo enigmatico"


Finalmente el mensaje ha quedado descifrado, pero hay que tener en cuenta que aquí no se han expuesto todas las posibilidades. Es normal, cuando se inicia el criptoanálisis, que se tomen algunas hipótesis incorrectas. En estos casos, no queda más remedio que volver a empezar.


Referencias:
- Cryptanalysis a study of ciphers and their solution. Helen Fouché Gaines.