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

\[y^2 = x^3 + 486662x^2 + x\]

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))