Chiffres asymétriques¶
RSA¶
On prend de grands premiers aléatoires.
p = nextprime(random(10^100)) q = nextprime(random(10^100)) n = p*q
On calcule \(\phi(n)\) avec la formule (ne pas utiliser la fonction
eulerphi
qui commencerait par tenter de factoriser \(n\)).
phi = (p-1)*(q-1) e = 2^16+1 d = (1/e) % phi
Le chiffrement est simplement une puissance modulaire. Bien faire le calcul modulo \(n\) !
rsa(m,e,n) = lift(Mod(m,n)^e);
m = fromdigits(Vec(Vecsmall("Ça fonctionne parfaitement !")),256) c = rsa(m,e,n)
m2 = rsa(c,d,n) Strchr(digits(m2, 256))
Rabin¶
Avec un module \(n=pq\), \(p,q\) congrus à 3 modulo 4.
randomprimemod(n,a,k) = until(p%k==a,p=randomprime(n)); p = randomprimemod(10^100,3,4); q = randomprimemod(10^100,3,4); n = p*q;
enc_rabin(m,n) = [m^2%n,kronecker(m,n),m%2];
Écrire la fonction de déchiffrement associée :
dec_rabin(c,p,q) = { [m2,a,b] = c; m; }
m = random(n); dec_rabin(enc_rabin(m,n),p,q) == m
Courbe elliptique¶
On prend la courbe https://en.wikipedia.org/wiki/Curve25519 de Bernstein
sur \(\F_p^2\), \(p=2^{255} − 19\).
On va travailler avec de manière naïve avec Pari/GP, mais jeter un œil à https://cr.yp.to/ecdh/curve25519-20060209.pdf pour un aperçu de ce qu’on peut faire en pratique.
p = 2^255-19 e = ellinit([0,486662,0,1,0],p);
On prend pour générateur un point \(g\) de coordonnée \(x=9\).
x = Mod(9,p); issquare(x^3 + 486662*x^2 + x,&y); g = [x,y] ellisoncurve(e,g)
On vérifie qu’il est d’ordre
2^252 + 27742317777372353535851937790883648493
n = 2^252 + 27742317777372353535851937790883648493 [isprime(n), ellmul(e,g,n)]
C’est bon ! Alice construit sa clef en tirant un exposant a au hasard.
a = random(n) A = ellmul(e,g,a)
Pour chiffrer on crée une clef de session construite pour l’occasion
k = random(n); K = ellmul(e,g,k);
On chiffre sur la coordonnée x, en utilisant clef publique d’Alice et la partie secrète de la clef de session. On laisse dans le chiffré la partie publique de la clef de session.
chiffre(m,A,k) = lift([m * ellmul(e,A,k)[1], K]);
dechiffre(c,K,a) = lift(c / ellmul(e,K,a)[1]);
m = fromdigits(Vec(Vecsmall("ECC c'est trop facile")),256); [c,K] = chiffre(m,A,k)
Strchr(digits(dechiffre(c,K,a),256))