²⁴¹ views

Kernel: Python 2 (SageMath)

Conversión de mensajes en (grandes) enteros

La primera parte de esta sesión es técnica, pero necesaria. Para los criptosistemas modernos, que actúan sobre grandes enteros, necesitamos unas funciones que conviertan mensajes de texto en grandes enteros de un cierto rango, digamos $0<m<N$ .

La idea es elemental: a cada letra de un mensaje le asignamos un valor, y podemos ver un mensaje como un entero de muchas cifras escrito en una cierta base.

Por comodidad consideramos el código ASCII asociado a cada letra, o quizá el código UNICODE.

En Python, la función ord(c) devuelve el código UNICODE asociado al carácter c.

In [1]:

%load_ext sage

In [2]:

ord('A') # igual que el ASCII

Out[2]:

65

In [3]:

ord(' ') # igual que el ASCII

Out[3]:

32

In [4]:

ord(u'Ü') # NO en ascii, sí en UNICODE

Out[4]:

220

UNICODE tiene 65.535 caracteres posibles, pero en la práctica no usaremos valores por encima de 1000, que será la base a partir de ahora.

Un mensaje de texto, podemos interpretarlo como un entero largo en base 1000:

In [5]:

m="Esto"

In [6]:

map(ord,m)

Out[6]:

[69, 115, 116, 111]

Con nuestra convención de fijar como base 1000, este mensaje se interpreta como el entero $m=(69,115,116,111)_{1000}=069115116111$

In [7]:

ZZ( map(ord,m)[::-1], 1000) # cuidado, hay que cambiar el orden. 
# SAGE interpreta que las cifras están en orden creciente

Out[7]:

69115116111

In [8]:

# Suponemos que no tendremos caracteres raros; podemos limitar la base a 1000.
def mensaje_a_entero(m):
    return ZZ(map(ord,m)[::-1],1000)

In [9]:

m=mensaje_a_entero("""Esto es un mensaje muy muy largo, 
que se va a convertir en un entero gigantesco""")

In [ ]:

In [10]:

Out[10]:

69115116111032101115032117110032109101110115097106101032109117121032109117121032108097114103111044032010113117101032115101032118097032097032099111110118101114116105114032101110032117110032101110116101114111032103105103097110116101115099111

Ahora necesitamos la conversión contraria: de un entero muyyyy grande a un mensaje de texto. La idea es reescribir el entero $m$ en base 1000,

In [11]:

print m.digits(base=1000)

Out[11]:

[111, 99, 115, 101, 116, 110, 97, 103, 105, 103, 32, 111, 114, 101, 116, 110, 101, 32, 110, 117, 32, 110, 101, 32, 114, 105, 116, 114, 101, 118, 110, 111, 99, 32, 97, 32, 97, 118, 32, 101, 115, 32, 101, 117, 113, 10, 32, 44, 111, 103, 114, 97, 108, 32, 121, 117, 109, 32, 121, 117, 109, 32, 101, 106, 97, 115, 110, 101, 109, 32, 110, 117, 32, 115, 101, 32, 111, 116, 115, 69]

Y usar la siguiente función para convertir cada entero en un carácter UNICODE:

In [12]:

# Para dar la vuelta...
print unichr(220)

Out[12]:

Ü

La función print es necesaria, si no se usa, sale algo raro:

In [13]:

unichr(220)

Out[13]:

u'\xdc'

In [14]:

def entero_a_mensaje(m):
    return u"".join(map( lambda x: unichr(x), 
                       m.digits(base=1000)[::-1]))

In [15]:

Out[15]:

69115116111032101115032117110032109101110115097106101032109117121032109117121032108097114103111044032010113117101032115101032118097032097032099111110118101114116105114032101110032117110032101110116101114111032103105103097110116101115099111

In [16]:

print entero_a_mensaje(m)

Out[16]:

Esto es un mensaje muy muy largo, 
que se va a convertir en un entero gigantesco

Todavía tenemos que resolver un pequeño problema: si nuestra clave privada es $N$ , y necesariamente ha de ser $0<m<N$ , ¿Cuántos caracteres caben en un mensaje?

La idea es contar bits: si $N\sim 2^b$ , entonces los mensajes pueden tener un número de caracteres $l=\lfloor \log_{1000} 2^b\rfloor.$

In [17]:

bits=1024 # tamaño de las claves modernas
longitud=floor(log(2^bits,1000))

In [18]:

longitud

Out[18]:

102

Redondeando, mandamos los mensajes de 100 en 100 caracteres.

In [19]:

m="""Lorem ipsum dolor sit amet, consectetur adipisicing elit, 
sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. 
Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris 
nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in 
reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla 
pariatur. Excepteur sint occaecat cupidatat non proident, sunt in 
culpa qui officia deserunt mollit anim id est laborum."""

In [20]:

def romper(m, t):
    l= [ m[i:i+t]  for i in  range(0, len(m), t) ]
    return l

In [21]:

print romper(m,100)

Out[21]:

['Lorem ipsum dolor sit amet, consectetur adipisicing elit, \nsed do eiusmod tempor incididunt ut labor', 'e et dolore magna aliqua. \nUt enim ad minim veniam, quis nostrud exercitation ullamco laboris \nnisi ', 'ut aliquip ex ea commodo consequat. Duis aute irure dolor in \nreprehenderit in voluptate velit esse ', 'cillum dolore eu fugiat nulla \npariatur. Excepteur sint occaecat cupidatat non proident, sunt in \ncu', 'lpa qui officia deserunt mollit anim id est laborum.']

In [22]:

mi=map(mensaje_a_entero, romper(m,100))
print mi

Out[22]:

[76111114101109032105112115117109032100111108111114032115105116032097109101116044032099111110115101099116101116117114032097100105112105115105099105110103032101108105116044032010115101100032100111032101105117115109111100032116101109112111114032105110099105100105100117110116032117116032108097098111114, 101032101116032100111108111114101032109097103110097032097108105113117097046032010085116032101110105109032097100032109105110105109032118101110105097109044032113117105115032110111115116114117100032101120101114099105116097116105111110032117108108097109099111032108097098111114105115032010110105115105032, 117116032097108105113117105112032101120032101097032099111109109111100111032099111110115101113117097116046032068117105115032097117116101032105114117114101032100111108111114032105110032010114101112114101104101110100101114105116032105110032118111108117112116097116101032118101108105116032101115115101032, 99105108108117109032100111108111114101032101117032102117103105097116032110117108108097032010112097114105097116117114046032069120099101112116101117114032115105110116032111099099097101099097116032099117112105100097116097116032110111110032112114111105100101110116044032115117110116032105110032010099117, 108112097032113117105032111102102105099105097032100101115101114117110116032109111108108105116032097110105109032105100032101115116032108097098111114117109046]

In [23]:

print "".join(map(entero_a_mensaje, mi))

Out[23]:

Lorem ipsum dolor sit amet, consectetur adipisicing elit, 
sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. 
Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris 
nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in 
reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla 
pariatur. Excepteur sint occaecat cupidatat non proident, sunt in 
culpa qui officia deserunt mollit anim id est laborum.

In [ ]:

Generación de claves para RSA

Cada usuario necesita un par de claves, que se generan de la siguiente forma:

Se eligen primos $p$ y $q$ , y $N=pq$ , con $N\sim 2^{1024}$ , o en general con $b$ bits y $N\sim 2^b$ .
Sabemos que $\varphi(N)=(p-1)(q-1)$ . Sea $0<E<\varphi(N)$ aleatorio, y $Ed\equiv 1\pmod{\varphi(N)}$ .
Entonces, $K=(N, E)$ y $k=(N,d)$ .

Implementamos este algoritmo en SAGE/Python.

In [24]:

def generar_claves(bits):
    b=bits//2
    p = ZZ.random_element(2^b, 2^(b+1)).next_prime()
    q = ZZ.random_element(2^b, 2^(b+1)).next_prime()
    print p,q
    N=p*q
    phi=(p-1)*(q-1)
    E=ZZ.random_element(3, phi)
    while gcd(E,phi)!=1:
        E=ZZ.random_element(3, phi)
    d=Mod(E,phi)^(-1)
    publica=(N,E)
    privada=(N,ZZ(d))
    return [privada, publica]

Veamos un ejemplo pequeño:

In [25]:

K_A, k_A=generar_claves(64)

Out[25]:

7572218077 5870357981

In [26]:

K_A

Out[26]:

(44451630822189422537, 24346995791228489083)

In [27]:

k_A

Out[27]:

(44451630822189422537, 2221956545144425747)

In [28]:

Mod(K_A[1]*k_A[1], euler_phi(K_A[0]) )

Out[28]:

1

En este caso...

In [29]:

factor(K_A[0])

Out[29]:

5870357981 * 7572218077

Pero si

In [30]:

K_A, k_A=generar_claves(1024)

Out[30]:

17027686238602965181551376188119714209187798144921085561027790810254426737731741867624339562304535068063455728047747916128594062170492103768240800765118213 19511477172757903991995282880834203554455639776691287077476132539072617312031938318179404626497226019849018975177479322815448305296883238177786356706033357

In [31]:

K_A

Out[31]:

(332235311349385651686030842228711691727082207615684531004930704973982463641500449463592834698186039456806248745097986669507130701462290530327012359596429128992783016032576016641050697997732861690792509034423978303683909961840449913029224394817781380308019715593897559552217670568784392249475547066408426231041,
 272384549757098539722712095332709657811891821133059546529239292706296643722149481811561043808283899956883214937374283823300040568421050371233658832096625989915148694151854801006294973291693180277901337314386260376899882019313037673229361448584555855764256889309898140039141385517992256316109017730330987874187)

entonces, no habremos terminado la factorización cuando vuelvan los Valar.

In [32]:

# K_A[0].factor() ### muyyyyyyy lento.

Las funciones de encriptación y desencriptación son la misma, pero las vamos a codificar por separado.

In [33]:

def F(K, m):
    return ZZ(Mod(m,K[0])^K[1])

def G(k, M):
    return ZZ(Mod(M,k[0])^k[1])

Supongamos que Bob quiere enviar un mensaje a Alicia:

In [34]:

m="La fuerza es intensa en ti, Joven Padawan"

In [35]:

m=mensaje_a_entero(m)

In [36]:

Out[36]:

76097032102117101114122097032101115032105110116101110115097032101110032116105044032074111118101110032080097100097119097110

$K_A$ es pública, todo el mundo puede encriptar PARA Alicia:

In [37]:


M=F(K_A,m)

In [38]:

Out[38]:

3270462264501074672167978135002485707874697181910581891695864041387475815934327025565106065519550393137555549961754631833526158799300273986222028277723561112013983146582466113710876467320802795653951562913203131938097910022997013291409948426499851065398676182573744089217919748120430008322409735672634420688

In [39]:

print entero_a_mensaje(M)

Out[39]:

ģƙδƪǳ͓AƎʤ¶Ƚ˨YÙΗˬxłƙ˟ʠɺƤʰ̯ΦŇȵjAȇȦƉȫȥρ˲ɷ́Ȏ̟ĬđϚÞĕ˓ȱp

Sólo Alicia conoce $k_A$ , y puede hacer

In [40]:

G(k_A, M)

Out[40]:

76097032102117101114122097032101115032105110116101110115097032101110032116105044032074111118101110032080097100097119097110

In [41]:

print entero_a_mensaje(G(k_A, M))

Out[41]:

La fuerza es intensa en ti, Joven Padawan

Ejercicios (¡Cómo no!)

Ejercicio 1

Fabiola y Gerardo deciden usar un cifrado RSA para comunicarse entre ellos, de ${512}$ bytes. Fabiola, con las prisas, ha generado una clave débil.

Nerea, una empleada de la odiosa NSA, ha averiguado que la clave pública de Fabiola tiene un factor poco mayor que $10^6$ .

Recuerde que si Fabiola tienen clave pública y secreta $K_{F}=(N_{F}, K_{F}), \quad k_{F}=(N_{F},k_{F}),$ respectivamente, y Gerardo quiere enviar un mensaje cifrado a Fabiola, entonces la codificación es $m\mapsto m^{K_{F}} \pmod {N_F}$

La clave pública de Fabiola es

clave_Publica_Fabiola=(59161016688734501272304157323482278706318510618483673988614119936145464124529420533,25137086551917962745723331611669263997540287445807291307495345691396569224365116213)

Nerea ha interceptado el siguiente mensaje:

19667433705242103609939245250795095287168144320505938303939982276722021548889547183

Rompa la clave pública de Fabiola
Decodifique el mensaje.

In [42]:

clave_Publica_Fabiola=(59161016688734501272304157323482278706318510618483673988614119936145464124529420533,25137086551917962745723331611669263997540287445807291307495345691396569224365116213)

In [43]:

M=19667433705242103609939245250795095287168144320505938303939982276722021548889547183

In [44]:

NF=clave_Publica_Fabiola[0]
EF=clave_Publica_Fabiola[1]
dF=ZZ(Mod(EF,euler_phi(EF))^(-1))
print entero_a_mensaje(G( (NF,dF), M ))

Out[44]:

%Ÿƃ͊OâʄĎɥż^PˁϓƝ̡̍͜ˀƼÍͱ!M̺Ά˷

Ejercicio 2 Implementa el cifrado de ElGamal de forma parecida a lo que hemos hecho con el RSA.

Conversión de mensajes en (grandes) enteros

Generación de claves para RSA

Ejercicios (¡Cómo no!)

Product

Resources

Company