CoCalc Public FilesMisc / Approximate GCD.sagewsOpen with one click!
Author: Gabriel Chênevert
Views : 107
Compute Environment: Ubuntu 18.04 (Deprecated)

Problème du PGCD approximatif

Consiste à récupérer la clé privée pp à partir d'un certain nombre de messages chiffrés xi=qip+ri x_i = q_i p + r_i pour le cryptosystème de van Dick et al. (cf. Section 5: Known attacks).

def gen_p(psize): p = random_prime(2^psize, lbound=2^(psize-1)) return p def gen_x(p,qsize,rsize): q = ZZ.random_element(2^(qsize-1), 2^qsize ) r = ZZ.random_element(2^(rsize-1), 2^rsize ) x = q*p+r return x

1) Avec seulement deux échantillons

psize = 500 qsize = 100 rsize = 80 p = gen_p(psize) x1 = gen_x(p,qsize,rsize) x2 = gen_x(p,qsize,rsize) p
2079916232028056584899565529874430566107774791822118887174635943000850940228961649283357879979398668667250796354306043902139316421295032957624437797329

1.1) Force brute sur les restes

On essaie toutes les valeurs possibles pour r1r_1 et r2r_2: on trouve forcément pp parmi les PGCD(x1r1,x2r2)\mathrm{PGCD}(x_1 - r_1, x_2 - r_2) qui ont un facteur premier de la bonne taille...
%time lbound = 2^(psize-1) print "Candidats pour p:" for r1 in range(2^rsize): for r2 in range(2^rsize): d = gcd(x1 - r1, x2 - r2) if d >= lbound: poss = factor(d)[-1][0] if poss >= lbound and poss < 2*lbound: print poss
Candidats pour p:
Error in lines 3-9 Traceback (most recent call last): File "/projects/c4a32d58-ff58-4533-b6dc-9042362fb3fa/.sagemathcloud/sage_server.py", line 875, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> MemoryError
CPU time: 0.00 s, Wall time: 0.00 s
10 secondes pour rsize=10, \approx 3 minutes pour rsize=12

1.1') Un tout petit peu moins brutal

En ne calculant le PGCD que lorsque x1r1x_1 - r_1 a un grand facteur premier (déterminé ici par l'algorithme de factorisation par défaut):
%time lbound = 2^(psize-1) print "Candidats pour p:" for r1 in range(2^rsize): if factor(x1 - r1)[-1][0] > lbound: for r2 in range(2^rsize): d = gcd(x1 - r1, x2 - r2) if d >= lbound: #poss = factor(d)[-1][0] poss = d if poss >= lbound: # and poss < 2*lbound: print poss
Candidats pour p:
Error in lines 3-11 Traceback (most recent call last): File "/projects/c4a32d58-ff58-4533-b6dc-9042362fb3fa/.sagemathcloud/sage_server.py", line 875, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> MemoryError
CPU time: 0.00 s, Wall time: 0.00 s
Pas forcément plus rapide (dépend polynomialement de psize)

1.2) Fractions continues

# en cours
%time res = [] print "Candidats pour p:" for frac in continued_fraction(x1/x2).convergents(): g = frac.numerator() h = frac.denominator() if g: # recherche plutôt brutale found = false #k = min(floor(x1/g), floor(x2/h))-2 k = floor((x1+x2)/(g+h))-2 cur1 = k*g-x1 cur2 = k*h-x2 curmin = Infinity while not found: cur1 += g cur2 += h k += 1 # print k, cur1, cur2 newmin = max(abs(cur1),abs(cur2)) if newmin < curmin: curmin = newmin curk = k else: found = true if is_prime(curk) and curk >= 2^(psize-1) and curk < 2^psize: print curk
Candidats pour p: 2079916232028056584899565529874430566107774791822118887174635943000850940228961649283357879979398668667250796354306043902139316421295032957624437797329 CPU time: 0.55 s, Wall time: 0.55 s
Ne trouve pas à tous les coups; mais quand ça marche, ça marche VITE

2) Avec plusieurs échantillons

Idée: étant donnés {x0=q0p+r0x1=q1p+r1xn=qnp+rn \begin{cases} x_0 = q_0 p + r_0 \\ x_1 = q_1 p + r_1 \\ \vdots \\ x_n = q_n p + r_n \end{cases} on remarque que les combinaisons linéaires qix0q0xi=qir0q0riq_i x_0 - q_0 x_i = q_i r_0 - q_0 r_i sont atypiquement petites (les pp disparaissent), ça correspond donc à un court vecteur obtenu comme une combinaison linéaire à coefficients entiers q0(x1,,xn)+q1(x0,,0)++qn(0,,x0).-q_0 (x_1, \ldots, x_n) + q_1 (x_0, \ldots, 0) + \cdots + q_n (0, \ldots, x_0). factor(561)
# work in progress
n = 15 psize = 20 rsize = 5 qsize = 5 p = gen_p(psize) x = [ gen_x(p, qsize, rsize) for _ in [0..n] ]
M = matrix(ZZ, n+1) M[0,0] = 2^psize for i in [1..n]: M[0,i] = x[i] M[i,i] = x[0] print M print print M.LLL() # selon les lignes
[ 1048576 12870758 15668745 16228332 16228329 15668736 15668735 10632364 11191965 8953582 11751555 12311157 12311151 12870759 15668737 16787936] [ 0 10632369 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [ 0 0 10632369 0 0 0 0 0 0 0 0 0 0 0 0 0] [ 0 0 0 10632369 0 0 0 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 10632369 0 0 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 10632369 0 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 10632369 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 10632369 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 10632369 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 10632369 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 0 10632369 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 0 0 10632369 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 0 0 0 10632369 0 0 0] [ 0 0 0 0 0 0 0 0 0 0 0 0 0 10632369 0 0] [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10632369 0] [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10632369] [ -2097152 -4476778 559617 -559557 -559551 559635 559637 10 -1119192 3357574 -2238372 -3357576 -3357564 -4476780 559633 -1678765] [ -2097152 6155591 559617 -559557 -559551 559635 559637 10 -1119192 3357574 -2238372 -3357576 -3357564 -4476780 559633 -1678765] [ 0 0 10632369 0 0 0 0 0 0 0 0 0 0 0 0 0] [ 0 0 0 10632369 0 0 0 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 10632369 0 0 0 0 0 0 0 0 0 0 0] [ 1048576 2238389 5036376 -5036406 -5036409 5036367 5036366 -5 559596 -1678787 1119186 1678788 1678782 2238390 5036368 -4476802] [ 1048576 2238389 5036376 -5036406 -5036409 5036367 5036366 -5 559596 -1678787 1119186 1678788 1678782 2238390 -5596001 -4476802] [ -1048576 -2238389 -5036376 5036406 5036409 5596002 -5036366 5 -559596 1678787 -1119186 -1678788 -1678782 -2238390 -5036368 4476802] [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -10632369] [ -2097152 -4476778 559617 -559557 -559551 559635 559637 10 -1119192 3357574 -2238372 -3357576 -3357564 6155589 559633 -1678765] [ -4194304 1678813 1119234 -1119114 -1119102 1119270 1119274 20 -2238384 -3917221 -4476744 3917217 3917241 1678809 1119266 -3357530] [ 0 0 0 0 0 0 0 0 0 10632369 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 0 0 10632369 0 0 0 0] [ -6291456 -2797965 1678851 -1678671 -1678653 1678905 1678911 30 -3357576 -559647 3917253 559641 559677 -2797971 1678899 -5036295] [ 0 0 0 0 0 0 0 0 10632369 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 10632369 0 0 0 0 0 0 0 0]
short = M.LLL()[5] short
(1048576, 2238389, 5036376, -5036406, -5036409, 5036367, 5036366, -5, 559596, -1678787, 1119186, 1678788, 1678782, 2238390, 5036368, -4476802)
q = M.solve_left(short) q
(1, -1, -1, -2, -2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -2)
for i in [0..n]: print N(x[i] / q[i])
1.06323690000000e7 -1.28707580000000e7 -1.56687450000000e7 -8.11416600000000e6 -8.11416450000000e6 -1.56687360000000e7 -1.56687350000000e7 -1.06323640000000e7 -1.11919650000000e7 -8.95358200000000e6 -1.17515550000000e7 -1.23111570000000e7 -1.23111510000000e7 -1.28707590000000e7 -1.56687370000000e7 -8.39396800000000e6
p
559597