Funcionamiento a alto nivel de RSA

[arget]

Huolas criptógrafos. Tengo una duda bastante baladí sobre el RSA, pero no logro imaginarme cómo lo solucionan. Esto también puede servir a quién no logre entender el RSA, pues pondré un ejemplo sencillito para mostrar mi dudita.
El RSA en realidad solo define 3 algoritmos, el de generación de claves, de cifrado y de descifrado (estos dos últimos sirven para comprobación de firma y de firma respectivamente, ya lo veremos).
El primero consiste en:
1. Elegir primos p y q. Yo elijo p = 13 y q = 97
2. Calcular n = p * q = 13 * 97 = 1261
3. Calcular φ(n) [se lee "fi de n", donde φ es la función de Euler] = (p - 1) * (q - 1) = 12 * 96 = 1152
4. Elegir e tal que gcd(φ(n), e) = 1; e < φ(n). Esto es que el mcd de e y φ(n) sea 1 (en otras palabras que sean coprimos o primos relativos entre sí) y que e sea menor que φ(n). En este caso elijo e = 23 [no olvidemos que un primo es comprimo con todos los números].
5. Elegir d tal que haga verdadera la siguiente expresión: d * e mod φ(n) = 1 y d < φ(n). En este caso
d * 23 mod 1152 = 1; solo hay una opción que yo he obtenido mediante un pequeño programa que dejo al final, solo hay una opción: 551.

La clave pública es: KU = {e, n} = {23, 1261}
La clave privada es: KR = {d, n} = {551, 1261}

Ya tenemos nuestras claves. Ahora vamos al algoritmo de cifrado:
C = M^e mod n
Esto es que para cifrar hay que elevar el mensaje M a e y calcular el resto de su división entre n.
Defino una tupla M.
M = {'H', 'O', 'L', 'A'}
Según el ASCII tenemos M = {72, 79, 76, 65}
Siguiendo que M_0 = 72 y M_1 = 79 entenderéis esto:
C_0   = M_0^e mod n = 72^23 mod 1261 = 5,231755239×10^42 mod 1261 = 1133
C_1   = M_1^e mod n = 79^23 mod 1261 = 4,420008451×10^43 mod 1261 = 27
C_2   = M_2^e mod n = 76^23 mod 1261 = 1,814314713×10^43 mod 1261 = 253
C_3   = M_3^e mod n = 65^23 mod 1261 = 4,9774534×10^41   mod 1261 = 676
C     = {1133, 27, 253, 676}

Para descifrar es:
M' = C^d mod n
Si habéis entendido hasta aquí, esto también. Y lo siguiente igual:
M_0'  = C_0^d mod n = 1133^551 mod 1261 = 72
M_1'  = C_1^d mod n = 27^551   mod 1261 = 79
M_2'  = C_2^d mod n = 253^551  mod 1261 = 76
M_3'  = C_3^d mod n = 676^551  mod 1261 = 65
M'    = {72, 79, 76, 65} = {'H', 'O', 'L', 'A'}

Para firmar lo que se debe hacer es "cifrar" pero con tu clave privada, el receptor para comprobar que el mensaje ha sido cifrado por ti necesita "descifrar con tu clave pública".
PGP/GPG implementa cifrar y firmar a la vez, para esto primero calcula el hash del mensaje, lo firma (con la clave privada del emisor), lo añade al principio del mensaje (aquí suele comprimir mediante ZIP), despues cifra simétricamente tanto el hash como el mensaje mediante una clave de sesión aleatoria, cifra dicha clave mediante RSA con la clave pública del receptor, añade la clave cifrada al principio del mensaje y envía el paquete. El receptor recibe el paquete, descifra usando su clave privada la clave de sesión simétrica cifrada que se encuentra al inicio del paquete, con esta descifra el resto del paquete, descomprime extrae el hash firmado, comprueba que sea del emisor legítimo, calcula el hash del mensaje y compara el que acaba de calcular con el firmado. Punto. Simple, ¿eh?
Ni que decir tiene que no siempre se firma o se cifra, puede solo cifrarse o solo firmarse. Pero ni lo uno ni lo otro tienen que ver ahora con esto. Me he ido por las ramas.

De acuerdo, ahora viene mi pregunta.
El texto cifrado {1133, 27, 253, 676} se tiene que enviar como bits [gracias, Sara].
Bien, esto se representa en hexadecimal del siguiente modo {0x046D, 0x1B, 0xFD, 0x02A4}
Así que tenemos cuatro bytes: 04 6D 1B FD 02 A4, sin embargo, si yo envío esto, ¿cómo sabe el receptor qué bytes corresponden a un único byte? Porque está claro que la letra 72 que ocupa solo un byte, al cifrarse ocupa dos bytes, y para desifrarse habrá que tratarlo así.
Sé que esto no lo define el RSA, que este solo define esos tres (o cinco) algoritmos, por eso en realidad la pregunta es: ¿cómo lo implementa PGP/GPG?
Me puedo imaginar que separa los caracteres cifrados mediante bytes nulos, o, ahora que lo pienso, lo mismo no cifra carácter a carácter. Bueno, no sé, tengo la curiosidad, si alguien sabe decírmelo...
Gracias de antebrazo.

[AlbertoBSD]

Que tal, actualmente tengo pocos conocimientos de criptografia, sin embargo he estado programando con libgcrypt y creo que lo que se hace es lo siguiente.

El mensaje que pones de ejemplo 'HOLA' no lo manejan como 4 mensajes separados, lo que hace es convertirlo a un solo mensaje es decir concatena los 4 octetos en un solo numero Entero sin signo. Y se le aplica el procesos que ya mencionaste.

Al final al decifrarlo el programa no sabe que ese entero sin signo regresenta letras o algun otro dato.

M = 0x484F4C41
Numero: 1213156417

[arget]

Ah, vale, pero eso me parecía demasiado ineficiente, se necesitan hacer potencias enormes para mensajes de apenas 4 letras, incluso usando la potenciación binaria [ https://es.wikipedia.org/wiki/Exponenciaci%C3%B3n_binaria ]. Pero sí, debe ser así, haré pruebas midiendo tiempos y demás.
Gracias!

[AlbertoBSD]

en claves RSA el numero n puede llegar a ser de hasta 512 octetos en claves de 4096 bits. y los factores p y q serian almenos de 256 octetos cada uno es un numero muy tardado de procesar y por ello la criptografia asimetrica es mas lenta que la simetrica

[kub0x]

Buenas arget,

Realmente lo que haces es utilizar RSA como modo de bloque de cifrado y para eso hay alternativas mejores. Revisa el PCKS1# (https://tools.ietf.org/html/rfc3447) y verás que en su modo recomendado de firma pasa directamente todo el octeto, lo recomendable es pasar el hash del octeto.

Info adicional:

hace un tiempo se me ocurrio que colisionando el hash en N bits de un cert x509v3 lícito y uno falso podría dar a pie a una forgery de la firma digital al ser firmada por la CA. Así que pregunté a ver si realmente RSA utiliza la data como chunks, si se utiliza un digest para firmar es para acortar el chunk y hacerlo inferior al tamaño del módulo (en tu ejemplo no hasheas, pero es un ejemplo ). Revisa mi post: https://crypto.stackexchange.com/questions/26562/rsa-signature-forgery