CoCalc Public FilesRSA.sagewsOpen with one click!
Author: Juan Carlos Bustamante
Views : 84
Compute Environment: Ubuntu 18.04 (Deprecated)

RSA

La mécanique et quelques exemples

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

  • Clé publique : (a,n)(a,n)aa et m=(p1)(q1) m = (p-1)(q-1) sont relativement premiers, ce qui garantit que aa est inversible modulo mm,
  • Clé privé : (c,n)(c,n)cc est l'inverse de aa modulo mm.
  • Fonction d'encryption : y=xamodny = x^a \mod n
  • Déchiffrement x=ycmodnx= 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=(p1)(q1)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