| Hosted by CoCalc | Download

RSA

La mécanique et quelques exemples

On choisit n=pqn = pq, un nombre assez grand.

  • Clé publique : (a,n)(a,n) où aa et m=(p−1)(q−1) m = (p-1)(q-1) sont relativement premiers, ce qui garantit que aa est inversible modulo mm,

  • Clé privé : (c,n)(c,n) où cc est l'inverse de aa modulo mm.

  • Fonction d'encryption : y=xamod  ny = x^a \mod n

  • Déchiffrement x=ycmod  nx= y^c \mod n

Exemple

On se donne deux nombres premiers, p=43,q=59p=43, q=59, puis on calcule n=pqn=pq n

typeset_mode(True)

p=43
q=59
n=p*q
n
25372537

Pour l'encryption, on a besoin de m=(p−1)(q−1)m=(p-1)(q-1) et d'un nombre aa, inversible modulo nn. La chose la plus simple à faire (mais probablement pas si sécuritaire que ça, c'est de prendre a=a= un nombre premier). On doit calculer l'inverse de aa mod mm, chose qu'à la main serait faite avec l'algorithme d'Euclide et la relation de Bézout, mais on peut faire ici directement.

m=(p-1)*(q-1)
print "m = " , m
a=13
c=a.inverse_mod(m)
print "c = " , c
m = 2436 c = 937 
13.inverse_mod(2537)
1171 
13.inverse_mod(2537)
1171 
︠a065f52e-280a-49f6-88d9-6ae7a3d467e4i︠
%md
### Supposons que l'on veuille transmettre le message $x=1819$

Supposons que l'on veuille transmettre le message x=1819x=1819

x=1819
x^a
(x^a)%n
y=power_mod(x, a, n)
y
23868497851571070407096121625388370681044592386849785157107040709612162538837068104459
20812081
20812081
︠68fdd33f-9333-48c3-8049-3d7d735e9fe6︠
(y^c)%n
18191819
power_mod(y,c,n)
18191819

Remarque :

Faire l'exponentiation, puis la réduction modulaire dans notre cas est, à toutes fins pratiques, équivalent (l'ordi va assez vite pour que la différence soit imperceptibe). Voyons avec des nombres un peu plus grands

p_1=next_prime(10^10)
p_1
p_2 =random_prime(10^10)
p_2
n_1=p_1 * p_2
n_1
10000000019 1201237607 12012376092823514533 
a=random_prime(10^10)
a
667905419 
x=12345678910111213141516171819
x
12345678910111213141516171819 
%time power_mod(x,a,n_1)
11948623708869854250 CPU time: 0.00 s, Wall time: 0.00 s 
%time x^a


︠f63acbd4-dbc5-4796-98a9-c92d670eee1di︠
%md
Une petite fonction utile pour l'algorithme d'Euclide.

Une petite fonction utile pour l'algorithme d'Euclide.

def Div(a,b):
	return [floor(a/b), a%b]

Div(2537,13)
[195, 2]

Une de pirates!

10 pirates trouvent un sac avec des pièces d'or (égales).

  • Ils essayent de se partager les pièces de façon juste et équitable.

  • Ceci est impossible, car il leur reste une piece d'or. Un pirate fâché, qutte.

  • Les pirates restants essayent de se distribuer le buttin. Ceci est encore impossible, il leur reste deux pièces cette fois.

  • UDeux autres pirates quittent, et les autres recommencent. Il se trouve que cette fois, tout marche.

Quel est le nombre minimal de pièces ?

crt(1,2,10,9)
11 
crt(11,0,90,7)
371 
371%7
0