TD 5 - RSA

Exercice 1

On demandait de chiffrer le message représenté par l'entier $v$, il n'y avait donc qu'à calculer $v^e\mod n$ ...

In [1]:
p =  1113954325148827987925490175477024844070922844843
q =  1917481702524504439375786268230862180696934189293
e =  3
In [2]:
n = p*q
v = 1808808319415691415062465989446183136395423154715795462152356725976667671981921260211627443446049
In [3]:
# On l'affiche en hexadécimal ...
c = pow(v,e,n)
hex(c)
Out[3]:
'0x10a000004972030440233370fff100006020600010a000004972030440233370fff1000060206'

Et on voit bien quelque chose de louche :

10a00000 4972 0304 4023 3370 fff 10 0006 0206
000
10a00000 4972 0304 4023 3370 fff 10 0006 0206
(Et si on ne voit rien, la suite de l'énoncé explique ce qu'on aurait dû voir).

In [4]:
# On écrit un petite classe dont on aura besoin ensuite

from ent3 import * # contient inversemod 
class RSA:
    def __init__(self,p,q,e):
        assert miller_rabin(p)
        assert miller_rabin(q)
        n = p*q
        m = (p-1)*(q-1)
        d = inversemod(e,m)
        self.n = n; self.e = e
        self.p = p; self.q = q; self.d =d

    def crypt(self,x):
        assert x<self.n
        return pow(x, self.e,self.n)

    def uncrypt(self,y):
        assert y<self.n
        return pow(y,self.d, self.n)

Exercice 2

L'énoncé montrait la marche à suivre pour traiter les données lues sur la carte :

# valeur d'authentification : 48 octets lus à l'adresse 0800:
APDU envoyée : bcb0080030
30 00 0d 8c 39 8e 8f b2 31 d8 43 c7 38 06 cd 6d | 0...9...1.C.8..m
3e aa 30 d7 33 ab 49 65 35 15 ce af 36 62 ca 1c | >.0.3.Ie5...6b..
31 50 2a ab 33 b9 df 5e 37 fb 0d b7 3d 15 61 21 | 1P*.3..^7...=.a!
 (SW1,SW2) = (90, 0)
# On supprime les 3 de redondance tous les 4 octets

0 00 0d 8c 9 8e 8f b2 1 d8 43 c7 8 06 cd 6d
e aa 30 d7 3 ab 49 65 5 15 ce af 6 62 ca 1c
1 50 2a ab 3 b9 df 5e 7 fb 0d b7 d 15 61 21

# Et on obtient la valeur d'authentification en hexadécimal:
v=0x0000d8c98e8fb21d843c7806cd6deaa30d73ab4965515ceaf662ca1c1502aab3b9df5e7fb0db7d156121

On vérifie au passage que c'est bien le même $v$ que dans l'exercice 1 :

In [5]:
0x0000d8c98e8fb21d843c7806cd6deaa30d73ab4965515ceaf662ca1c1502aab3b9df5e7fb0db7d156121
Out[5]:
1808808319415691415062465989446183136395423154715795462152356725976667671981921260211627443446049

On recopie les données situées après le code "2E 02 38 F1", on doit lire

In [6]:
0x38
Out[6]:
56

56 octets, donc ...

In [7]:
 s='''30 04 97 20 33 04 40 23                   | =#a!..8ñ0.— 3.@#
33 37 0F FF 31 01 00 06 32 50 02 06 32 50 34 97 | 37.ÿ1...2P..2P4—
35 44 84 94 32 4F 4E 2F 34 D4 F4 E4 39 51 55 45 | 5D„”2ON/4Ôôä9QUE
32 02 02 02 30 20 20 20 32 02 02 02 30 20'''
In [8]:
# On peut nettoyer cette chaîne avec une expression régulière
# (ou à la main)
import re
pat=r'(\||\n)'
ll=re.split(pat,s)
ll
Out[8]:
['30 04 97 20 33 04 40 23                   ',
 '|',
 ' =#a!..8ñ0.\x97 3.@#',
 '\n',
 '33 37 0F FF 31 01 00 06 32 50 02 06 32 50 34 97 ',
 '|',
 ' 37.ÿ1...2P..2P4\x97',
 '\n',
 '35 44 84 94 32 4F 4E 2F 34 D4 F4 E4 39 51 55 45 ',
 '|',
 ' 5D\x84\x942ON/4Ôôä9QUE',
 '\n',
 '32 02 02 02 30 20 20 20 32 02 02 02 30 20']
In [9]:
mm=[ll[4*i] for i in range(len(ll)//4+1)]
mm
Out[9]:
['30 04 97 20 33 04 40 23                   ',
 '33 37 0F FF 31 01 00 06 32 50 02 06 32 50 34 97 ',
 '35 44 84 94 32 4F 4E 2F 34 D4 F4 E4 39 51 55 45 ',
 '32 02 02 02 30 20 20 20 32 02 02 02 30 20']
In [10]:
from functools import reduce
t=reduce(lambda x,y:x+y,mm)
t
Out[10]:
'30 04 97 20 33 04 40 23                   33 37 0F FF 31 01 00 06 32 50 02 06 32 50 34 97 35 44 84 94 32 4F 4E 2F 34 D4 F4 E4 39 51 55 45 32 02 02 02 30 20 20 20 32 02 02 02 30 20'
In [11]:
t=t.replace(' ','')
t
Out[11]:
'300497203304402333370FFF31010006325002063250349735448494324F4E2F34D4F4E4395155453202020230202020320202023020'
In [12]:
len(t)
Out[12]:
108
In [13]:
# On élimine les 3 de contrôle
x = ''
for i in range(len(t)//2):
    if i%4: x+=t[2*i:2*i+2]
    else: x+=t[2*i+1]

Et on obtient enfin les données de la carte C'est un encodage bizarre oà les chiffres hexadécimaux 0-9 sont utilisés pour représenter le numéro de la carte, des dates ou d'autres codes, et où les caractères alphabétiques sont représentés par leurs codes ascii ...

In [14]:
x
Out[14]:
'004972030440233370FFF101000625002062503497544849424F4E2F4D4F4E49515545202020202020202020202020'
In [15]:
from codecs import *
decode(x,'hex')
Out[15]:
b'\x00Ir\x03\x04@#3p\xff\xf1\x01\x00\x06%\x00 bP4\x97THIBON/MONIQUE            '

Il faut donc couper après l'octet 0x97 et interpréter la suite en ASCII. Voilà la structure des données

00
4972030440233370
FFF
101
0006
250
0206
250
3
497
THIBON/MONIQUE
(espaces)


00                      # Identique sur toutes les cartes
49**************        # Numéro de la carte
FFF                     # Réservé futurs numéros
101                     # Code usage (ou code service)
aamm                    # Début de validité
250                     # Code langue (250=français)
aamm                    # Fin de validité
250                     # Code devise (Franc)
3                       # Exposant (5=unité, 3=centimes)
497                     # ?? (identique sur toutes le cartes)
*****************       # Nom du titulaire, en ASCII, sur 26 caractères
202020202020202020202020# (des espaces)

Pour la fausse carte, il suffit donc de remplacer le nom, le numéro et les dates, puis de chiffrer les nouvelles données d'authentification avec la cléf privéee $d$.

In [16]:
x = b'004972030440233370FFF101000625002062503497544849424F4E2F4D4F4E49515545202020202020202020202020'
y = b'003141592653589793FFF101000025013132303497'
len(y)
Out[16]:
42
In [17]:
z = encode(b'MANSOIF/GERARD','hex')
len(z)
Out[17]:
28
In [18]:
z
Out[18]:
b'4d414e534f49462f474552415244'
In [19]:
y+z
Out[19]:
b'003141592653589793FFF1010000250131323034974d414e534f49462f474552415244'
In [20]:
len(y+z)
Out[20]:
70
In [21]:
y=y+z+b'20'*12
In [22]:
len(y)
Out[22]:
94
In [23]:
y
Out[23]:
b'003141592653589793FFF1010000250131323034974d414e534f49462f474552415244202020202020202020202020'
In [24]:
x
Out[24]:
b'004972030440233370FFF101000625002062503497544849424F4E2F4D4F4E49515545202020202020202020202020'
In [25]:
# Il ne reste plus qu'à réinsérer les 3

yy = b''.join([b'3'+y[7*i:7*i+7] for i in range(len(y)//7+1)])

yy
Out[25]:
b'300314153926535839793FFF31010000325013133230349734d414e5334f494632f47455324152443202020230202020320202023020'
In [26]:
len(yy) #petit contrôle
Out[26]:
108
In [27]:
## On fabrique la nouvelle valeur d'authentification en substitiuant 
## le nouveau numéro et les nouvelles dates (00/00 et 13/13)

uu =int('''
10a00000 3141 5926 5358 9793 fff 10 0000 1313
000
10a00000 3141 5926 5358 9793 fff 10 0000 1313
'''.replace(' ','').replace('\n',''),16)
In [28]:
uu
Out[28]:
33865723129921835612249160218012612201774316382006172730732123289398593691299921292272079635
In [29]:
rsa = RSA(p,q,e)
In [30]:
vv = rsa.uncrypt(uu)
vv
Out[30]:
93737746716878564284840231240552282287015996007177936369954585285163900606293377642619339275449
In [31]:
w = '%X' %vv
w
Out[31]:
'B3C0BC69935C2FB00E6A91054D4645971C50E0A8CBF69081F7D007207DB12912F49CFEEB1F7FCB9'
In [32]:
ww = ''.join(['3'+w[7*i:7*i+7] for i in range(len(w)//7+1)])
ww
Out[32]:
'3B3C0BC639935C2F3B00E6A931054D46345971C530E0A8CB3F69081F37D0072037DB129132F49CFE3EB1F7FC3B9'

Et voilà ! Il n'y a plus qu'à écrire $ww$ et $yy$ aux adresses indiquées, et à programmer la carte pour qu'elle réponde (0x90,0x00) quelque soit la question posée ...

In [33]:
## Exercice 2

from decimal import *           # Multiprécision sur les flottants
from ent3 import *

getcontext().prec = 5000        # On trouve ça dans la doc
e = Decimal("1.").exp()         # e = exp(1), et il connaît exp
e = str(e)

def s(i):                       # tranches de 20 chiffres consécutifs
    try:
        return int(e[2+i:2+i+20])
    except: return None


def test_slice(n):              # On teste q et p=2q+1 si q est impair
    if n%2 ==0: return False
    q = 2*n+1
    if miller_rabin(n):
        if miller_rabin(q): return True
    return False

for i in range(len(e)-22):
    if test_slice(s(i)):
        print (i+2, s(i), 2*s(i)+1)

850 18491463140934317381 36982926281868634763
1869 5724817658511806303 11449635317023612607

Le premier est donc $q=18491463140934317381$, à la position 850 après la virgule.

Exercice 3

On peut retrouver $y=x^3\mod n_an_bn_c$ par le théorème des restes chinois. Comme $x<\min(n_a,n_b,n_c)$ on peut le trouver en calculant la racine cubique de $y=x^3$ dans les réels. Pour utiliser Decimal, on calcule $y^{1/3} = \exp(\ln(y)/3).$

In [34]:
from codecs import encode, decode
def s2i(s):
    return int(encode(s,'hex'),16)

def i2s(m):
    t = '%x' % m         
    if len(t)%2: t='0'+t
    return decode(t,'hex')

from ent3 import *
from functools import reduce
def solve_chinese(yy,mm):
    assert len(yy) == len(mm), "Arguments must have same length."
    k = len(yy); m = reduce(lambda x,y:x*y, mm); x=0
    for i in range(k):
        u = reduce(lambda x,y:x*y, [mm[j] for j in range(k) if j!=i])
        v = inversemod(u,mm[i])
        x = (x + yy[i]*v*u) % m
    return x


e = 3

na = 2135987035920910082395022704999628797051095341826417406442524165008583957746445088405009430865999
nb = 2135987035920910082395022704999628797162490781344963051155377956280967195101981889839850702671619
nc = 2135987035920910082395022704999628896193030374617175691844152549530769669304774519830221356585511

ya = 1704530022978544318071261282029959269089776023381678967531907665026466268332863367550402288250742
yb = 1704520499835949615592131996885727697345627882180875786884636832758759452639025264678208940201982
yc = 1696054426594054895613006544606777272432734244621789015588464666648043681903785330811909500673766


res = solve_chinese([ya,yb,yc],[na,nb,nc])
    
from decimal import *
getcontext().prec = 500
z = Decimal(res)
a = z.ln()/3
b = a.exp()

print (res)
print (b)

182604505278011806364889160347210631562705250523819775263426937816401785613989069256884639013849511605042503493462711546751975744
5673318464228055404789402258300850215739763.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999920
In [35]:
int(str(b.to_integral_exact()))
Out[35]:
5673318464228055404789402258300850215739764
In [36]:
i2s(_)
Out[36]:
b'A bon chat bon rat'
In [ ]:
In [ ]: