mercoledì 30 aprile 2014

Osservazioni sul logaritmo discreto e la fattorizzazione dei numeri RSA


L'algoritmo del confronto

Confrontare i due insiemi numerici:(1, 3, 5, 7) e (0, 2, 3, 4, 7) e dire se esistono elementi uguali tra il primo insieme e il secondo insieme
posizione
Primo vettore
Secondo vettore
confronto
0

0

1
1


2

2

3
3
3
uguali
4

4

5
5


6



7
7
7
uguali

Algoritmo estendibile a più insiemi di vettori numerici. Per ottimizzare il metodo i numeri di posizione vengono elencati tra il minimo e il massimo valore degli insiemi da confrontare: questo minimizza le celle vuote e quindi lo spreco di memoria. Questo metodo può essere usato per programmare un PC a fare le operazioni insiemistiche di unione e intersezione: l'intersezione l'abbiamo già spiegata, l'unione sono tutti gli elementi comuni e non comuni presi una sola volta.


altri programmi di utilità

Il test di ingresso: strategie matematiche per superarlo

sabato 26 aprile 2014

Fattorizzazione: metodo QR quadro

n=pq (RSA)
k dispari allora posso scrivere:
n-kp=2(a+n/p) e ponendo v = n-2a ho l'equazione di II grado
kp^2-vp+2n=0, v> sqrt(8nk)
Si poteva anche considerare il caso n-kp=2(n/p-a) ma è del tutto analogo con la sola differenza che v=n+2a

k pari allora posso scrivere
n-kp = 2(a+n/p)+ 1 e ponendo v = n-2a-1 ho l'equazione di II grado kp^2-vp+2n=0, v> sqrt(8nk)
Si poteva anche considerare il caso n-kp=2(n/p-a)+1 ma è del tutto analogo con la sola differenza che v=n+2a-1

Nota: se k dispari allora v dispari, se k pari allora v pari

Stabilisco oltre a n anche il valore di k (k varia per ogni PC - calcolo parallelo). Il valore di k è molto importante. L'algoritmo per funzionare ha bisogno di un valore di k intero con k > p/q dove p> q ovvero k=2, 3, 4, 5, .... Negli RSA dove la dimensione di p è circa quella di q ,k può assumere un valore basso da 2 a 100 (massimo). In ogni caso k < n/8 come si può facilmente provare
risolvo l'equazione di II grado finché non trovo le soluzioni intere facendo variare il valore del parametro v.

In Python

import math;
def fact(n, k):
v = math.floor(math.sqrt(8*n*k));
delta = math.sqrt(math.fabs(v*v-8*n*k));
p = (v-delta)/(2*k);
q = (v+delta)/(2*k);
while p != math.floor(p) and q != math.floor(q):
v = v+1;
delta = math.sqrt(math.fabs(v*v-8*n*k));
p = (v-delta)/(2*k);
q = (v+delta)/(2*k);
if p == math.floor(p):
print(p);
print(n/p);
else:
print(q);
print(n/q);

Con semplici considerazioni algebriche si può pervenire in modo altrettanto valido anche alle altre equazioni del tipo kp^2+vp-2n=0, kp^2+vp+2n=0, kp^2-vp-2n=0, kp^2-vp+2n=0. Quindi possiamo scrivere anche (dove k>p/q , k = 2, 3, 4, ,.... per numeri RSA)

import math;
def fact(n, k):
v = 0;
delta = math.sqrt(math.fabs(v*v+8*n*k));
p = (v-delta)/(2*k);
q = (v+delta)/(2*k);
while p != math.floor(p) and q != math.floor(q):
v = v+1;
delta = math.sqrt(math.fabs(v*v+8*n*k));
p = (v-delta)/(2*k);
q = (v+delta)/(2*k);
if p == math.floor(p):
print(p);
print(n/p);
else:
print(q);
print(n/q);

venerdì 25 aprile 2014

Altri algoritmi per fattorizzare i numeri con il Mathematica

Si consiglia di usare comunque l'ultima versione del software e all'occorrenza di impostare i calcoli con un elevato numero di cifre decimali
------
n := 187
b := 1
a := N[Sqrt[n+b^2]]
While[a != Floor[a], b=b+1; a := N[Sqrt[n+b^2]] ]
p := a-b
q := a+b
Print[p]
Print[q]
-----------------------
n := 187
a := Floor[N[Sqrt[n]]]
b := N[Sqrt[Abs[a^2-n]]]
While[ b != Floor[b], a = a+1; b := N[Sqrt[Abs[a^2-n]]]]
p := a-b
q := a+b
Print[p]
Print[q]
-------------------------
n := 187
i := 1
p := GCD[10^i-1, n]
While[p==1, i=i+1;p := GCD[10^i-1, n] ]
Print[p]
Print[n/p]
----------------------------

Nota
Per aumentare la precisione e il numero delle cifre significative si può usare la funzione N[], con la specifica ad esempio N[, 100] per calcoli con 100 cifre significative

La teoria dei numeri con il software Mathematica

Di seguito  esempi di codice (anche programmazione) con il software Mathematica per applicazioni nella teoria dei numeri

FATTORIZZAZIONE CON ALGORITMO  EQUAZIONE DI II GRADO
n := 2535311
s := 2*Floor[N[Sqrt[n]]]
delta := N[Sqrt[Abs[s*s-4*n]]]
While[delta != Floor[delta],s=s+2;delta := N[Sqrt[Abs[s*s-4*n]]]]
p := (s-delta)/2
q := (s+delta)/2
Print[p]
Print[q]

FATTORIZZAZIONE CON IL FATTORIALE
n := 187
s := Floor[N[Sqrt[n]]]
GCD[n, s!]

FATTORIZZAZIONE CON ATTACCO FORZA BRUTA
n := 2535311
i = 3
While[n/i != Floor[n/i],i=i+2]
Print[i]
Print[n/i]

n := 1234567891273
i := 3
While[Mod[n, i]!=0, i= i+2]
Print[i]
Print[n/i]

LISTA DEI NUMERI PRIMI
i := 1
While[i <= 100, Print[Prime[i]]; i = i+1]

Table[Prime[n], {n, 1, 100}]

TEST DI PRIMALITA'
PrimeQ[789]

FATTORIZZAZIONE
FactorInteger[187]

PHI DI EULERO
EulerPhi [67]

POTENZE MODULO N (2^34 mod 3)
PowerMod[2, 34, 3]

LOGARITMO DISCRETO (7^i = 2 mod 11)
i := 2
While[PowerMod[7, i, 11] != 2, i=i+1]
Print[i]

DIVISORI DI UN NUMERO
Divisors[86]

VERIFICA IPOTESI DI RIEMANN
i := 1
While[i<=100, Print[Zetazero[i]]; i=i+1]

For[i= 1, i < 100, i++, Print[Zetazero[i]]

Table[N[ZetaZero[i]], {i, 1, 10}] per una verifica cliccate qui (versione on line del Mathematica)
oppure N[Table[ZetaZero[i], {i, 1, 24}]]

a livello grafico Plot[Abs[Zeta[1/2+x*I]], {x, 0, 40}] o cliccate qui
Plot[(Re[Zeta[1/2+x*I]], Im[Zeta[1/2+x*I]]), {x, 0, 40}] o cliccate qui

martedì 22 aprile 2014

Algoritmi ausiliari: calcolo potenze modulo n e calcolo periodo soluzioni in Diffie-Helmann

calcolo del periodo in a^x = b mod p, p primo
p primo MCD(a, p)= 1
programma in python
import math;
def periodo(a,p):
 i = 2;
 while( (a**i) % p != 1 or (p-1) % i != 0):
  i = i+1;
 print(i); 
-------------------------------------------------
calcolo potenza a^m mod n dove:
MCD(a, n) = 1
m > phi(n)
a^m nod n

programma in PARI/GP
{potenza(a, m, n) = local(c, d);
c = m % eulerphi(n);
d = (a^c) % n;
print(d);
}

lunedì 21 aprile 2014

Il teorema delle soluzioni del logaritmo discreto


Vedremo che beta nel primo caso oltre a essere intero potrebbe anche essere un divisore di p-1, mentre nel secondo caso può essere un divisore di phi(n).

Oltre alle soluzioni logaritmo discreto il teorema ci suggerisce un metodo per calcolare ad esempio :
a^q mod n con MCD(a,n)=1
Infatti se q = k*phi(n)+l allora a^q = a^l mod n

Altre applicazioni: la fattorizzazione dei numeri interi (RSA) se n=pq p, q primi s =p+q
a^s = b mod (n) con b =a^(n+1) mod n e s > 2*sqrt(n) .
Trovato s (e tutti i valori in progressione aritmetica che soddisfano a^s=b mod n),i valori di p, q si trovano risolvendo l'equazione x^2-sx+n=0

Inoltre il più piccolo intero e positivo tale che a^e = 1 mod p deve essere un divisore di p-1 perché
p-1=ke+r con 0<=r < e => r = 0 (a^(p-1) = 1 mod p, MCD(a,p)=1) Questo prova perché le soluzioni del logaritmo discreto sotto le opportune ipotesi di cui sopra sono tutte equidistanti ovvero in media aritmetica con ragione d dove d | p-1.  a^e = 1 mod p allora y=x+be è tale che a^y= a^x = b mod p MCD(a,p)=1 .Quindi y = x+be  è soluzione di a^x = b mod p , p primo e x soluzione data. Idem per a^x = b mod (n) dove MCD(a,n)=1, y= x+be è soluzione con e | phi(n)
Nell'equazione a^x = b mod p, con p primo (siamo qui nelle ipotesi di Diffie-Helmann) il periodo che caratterizza tutte le soluzioni in progressione aritmetica si calcola trovando il valore minimo tale che a^d=1 mod p, d = periodo della progressione aritmetica delle soluzioni. Tale valore come sopra provato deve essere un divisore di p-1

domenica 20 aprile 2014

I divisori di un numero senza ripetizioni

Trovare tutti i divisori di un numero senza ripetizioni. Applicazioni: teoria dei numeri, logaritmo discreto

import math;
def divisori(n):
 j = 1;
 while (j < math.floor(math.sqrt(n))):
  if n % j == 0:
   print(j);
   print(n/j);
   j = j+1;
  else:
   j =j+1;

Ancora formule per problemi RSA

Dalla relazione sempre verificata p^2+q^2=s^2-2n, s=p+q, n=pq, ottengo sapendo che q=n/p
p^4+p^2(2n-s^2)+n^2=0
p^2 = [V+sqrt(V^2-4n^2)]/2
q^2 = [V-sqrt(V^2-4n^2)]/2
V=s^2-2n => V > 2n, s^2>4n

V deve essere pari perché differenza di due pari

Oppure p^2+q^2 = s^2-2n, p^2 q^2 = n^2 =>
X^2-(s^2-2n)X+n^2=0, X=p^2, q^2
X=[V+sqrt(V^2-4n)]/2, V> 2n
X=[V-sqrt(V^2-4n)]/2, V> 2n

In generale non è molto efficiente .....

import math;
def facto(n):
 V = 2*n;
 delta = V*V-4*n*n;
 p = math.sqrt((V+math.sqrt(delta))/2);
 while (n%p != 0):
  V = V+2;
  delta = V*V-4*n*n;
  p = math.sqrt((V+math.sqrt(delta))/2);
 q = n/p;
 print(p);
 print(q);

sabato 19 aprile 2014

Crivello per la fattorizzazione con le equazioni di II grado

ogni numero primo può terminare solo con una della cifre 1, 3, 7, 9
sia n = pq dove p, q sono numeri primi
In base alla seguente tabella moltiplicativa:
X 1 3 7 9
1 1 3 7 9
3 3 9 (2)1 (2)7
7 7 (2)1 (4)9 (6)3
9 9 (2)7 (6)3 (8)1
il numero n = pq con p, q primi può terminare a sua volta con una delle seguenti cifre finali: 1, 3, 7, 9
Sia n =pq, s = p+q, d =p-q
in base quindi alla tabella abbiamo il seguente schema:
se l'ultima cifra di n = pq è:
  • cifra finale di n è 3 allora abbiamo le seguenti combinazioni per le cifre finali di p, q:  (3,1), (7, 9) quindi la somma s=p+q deve terminare con una delle cifre 4, 6; mentre la differenza d=p-q con una delle cifre 2, 8
  • cifra finale di n è 1 allora abbiamo le seguenti combinazioni per le cifre finali di p, q:  (9,9), (1, 1), (3, 7) quindi la somma s=p+q deve terminare con una delle cifre 0, 2, 8; mentre la differenza d=p-q con una delle cifre 0, 4, 6 
  • cifra finale di n è 9 allora abbiamo le seguenti combinazioni per le cifre finali di p, q:  (3,3), (1, 9), (7, 7) quindi la somma s=p+q deve terminare con una delle cifre 0, 4, 6; mentre la differenza d=p-q con una delle cifre 0, 2, 8
  • cifra finale di n è 7 allora abbiamo le seguenti combinazioni per le cifre finali di p, q:  (3,9), (7, 1) quindi la somma s=p+q deve terminare con una delle cifre 2,  8; mentre la differenza d=p-q con una delle cifre 6, 4
Queste considerazioni ci possono essere molto utili in algoritmi di fattorizzazione del tipo x^2-sx+n=0 dove s^2-4n > 0 e x=p, q. Inoltre dato che s^2-4n deve essere un quadrato perfetto è facile vedere che un quadrato perfetto deve terminare con una delle cifre 0, 1, 4, 5, 6, 9. Infatti basta osservare la tabella:

I I^2
0 0
1 1
2 4
3 9
4 16
5 25
6 36
7 49
8 64
9 81
  e questo aumenta ulteriormente la velocità nella ricerca delle soluzioni


le soluzioni del Logaritmo discreto e le progressioni aritmetiche

TEOREMA
dato il logaritmo discreto a^x = b mod n con a, b, n noti se esiste una soluzione allora ne esistono infinite e tutte le soluzioni sono in progressione aritmetica se:
a) n è primo
oppure se
b) n,non è una potenza perfetta e  b ,non è una potenza perfetta

inoltre se n è primo la ragione d | (n-1)
mentre se n=pq con p, q primi allora la ragione d | (p-1)(q-1)

Se n=pq, con p, q primi, da a^(n-s+1)=1 mod (n) dove MCD(a,n)=1 ricordiamo che a^s=b, mod (n) , s=p+q >2*radq(n) a^(n+1) = b mod(n). Questo ci aiuta nella fattorizzazione di n spendo che i fattori si trovano , conosciuto s risolvendo x^2-sx+n=0.

Esempio 1)
7^x = 2 mod 11
si trova che x = 3 , x = 13, x = 23, ..... (soluzioni in progressione aritmetica con ragione 10 )

Esempio 2)
7^x = 4 mod 11
si trova che x = 6 , x = 16, x = 26, ..... (soluzioni in progressione aritmetica con ragione 10)

Esempio 3)
4^x = 9 mod 11
si trova che x = 3 , x = 8, x = 13, ..... (soluzioni in progressione aritmetica con ragione 5)

Esempio 4)
2^x = 9 mod 11
si trova che x = 6 , x = 16, x = 26, ..... (soluzioni in progressione aritmetica con ragione 10)

Esempio 5)
3^x = 15  mod 17
si trova che x = 6 , x = 22, x = 38, ..... (soluzioni in progressione aritmetica con ragione 16)

Esempio 6)
204^x = 34 mod 391
si trova che x = 15 , x = 37, x = 59, ..... (soluzioni in progressione aritmetica con ragione 22) qui molte in z_n.

Esempio 7)
9^x = 15 mod 33
si trova che x = 2 , x = 7, x = 12, ..... (soluzioni in progressione aritmetica con ragione 5)

Esempio 8)
3^x = 13 mod 17
si trova che x = 4 , x = 20, x = 36, ..... (soluzioni in progressione aritmetica con ragione 16)

quindi trovando le prime due soluzioni si ha la formula per trovare tutte le altre.


venerdì 18 aprile 2014

Programma BC: logaritmo discreto e fattorizzazione

FATTORIZZAZIONE CON BC (BRUTE FORCE)

n = 187;
scale = 0;
p = 3;
while ( n%p != 0 )
p = p+2;
print p;
print n/p;


LOGARITMO DISCRETO CON BC (BRUTE FORCE)
i = 80;
scale = 0;
while ((204^i) % 391 != 34)
i = i+1;
print i

in Python a^x = b mod n
import math;
def   logdisc(a, b, n):
i= 1;
while(a**i % n != b):
i = i+1;
print(i);

In PARI/GP
{logdisc(a, b, n) = local(i);
i = 1;
while(a^i % n != b, i=i+1);
print(i);
}

martedì 15 aprile 2014

RSA: ancora equazioni di II grado

n= pq => RSA

p-V = 2a, con V numeri dispari fissato qualsiasi

p-V = 2(q+b) =>

p-V = 2(n/p +b) =>

p^2-p(V+2b) -2n = 0

p = [(V+2b + sqrt((V+2b)^2+8n))/2] oppure
p = [(V+2b - sqrt((V+2b)^2+8n))/2]

M = V+2b => M dispari (V disapri, 2b pari) =>

p = (M+ sqrt(M^2+8n))/2; oppure
p = (M- sqrt(M^2+8n))/2;

p =MCD(n, p1)
q =MCD(n, p2)

M> sqrt(n) oppure M < sqrt(n)

Il metodo risulta particolarmente efficiente quando p/q è circa 1/2 e in RSA è caso abbastanza comune

import math;
def mcd(a, b):
 if  b == 0:
  return a;
 else:
  return mcd(b, a%b);
def facto(n):
 m = 3;
 delta = m*m+8*n;
 while (math.sqrt(delta) != math.floor(math.sqrt(delta))):
  m = m+2;
  delta = m*m+8*n;
 p = (m+math.sqrt(delta))/2;
 q = (m-math.sqrt(delta))/2;
 a = mcd(p, n);
 b = mcd(q, n);
 print(a);
 print(b);

domenica 13 aprile 2014

Fattorizzazione biquadratica RSA



Inoltre:

x^2-sx+n=0 x =p, q, n=pq, s=p+q, 
p = [s+sqrt(s^2-4n)]/2, q = [s-sqrt(s^2-4n)]/2

e dalla relazione 
p^2=sd+q^2, V=sd, q=n/p => p^4-Vp^2-n^2=0 => 

p=sqrt[(V+sqrt(V^2+4n^2))/2]
q=sqrt[(V-sqrt(V^2+4n^2))/2]

V>4sqrt(n) 4 | V

Un esempio in Python

import math;
def facto(n):
 V = 4 * math.floor(math.sqrt(n));
 s = math.sqrt(2*n + math.sqrt(V**2 +4*n**2));
 while (math.floor(s) != s):
  V = V+4;
  s = math.sqrt(2*n + math.sqrt(V**2 +4*n**2));
 x = (s+math.sqrt(s**2-4*n))/2;
 y = (s-math.sqrt(s**2-4*n))/2;
 print(x);
 print(y);

Il teorema della periodicità dei numeri RSA


teniamo anche presente che 4 | phi(n) e che in RSA deve essere phi(n) > e (chiave pubblica)
Osserviamo anche che in RSA phi(n) > e quindi n-s+1 > e ovvero  s = p+q < n+1-e . Questo ci può aiutare sia per limitare i valori di s sia quelli di phi(n). Ecco perché e non può essere troppo grande altrimenti e < phi(n) < n-2*sqrt(n)+1  potrebbe essere un intervallo piccolo per phi(n) oppure 2*sqrt(n) < s < n+1-e potrebbe essere anche qui troppo piccolo il range per s

Una implementazione in Python molto semplificata e non ottimizzata è:

import math;
def mcd(a, b):
 if  b == 0:
  return a;
 else:
  return mcd(b, a%b);
def facto(m):
 g = 1;
 h = mcd(m, 10**g-1);
 while (h == 1):
  g = g+1;
  h = mcd(m, 10**g-1);
 print(h);
 print(m/h);

sabato 12 aprile 2014

Fattorizzare gli RSA con la tecnica dei numeri periodici

Ecco una applicazione in Python della fattorizzazione degli RSA usando la periodicità dei numeri

import math;
def mcd(a, b):
 if  b == 0:
  return a;
 else:
  return mcd(b, a%b);
def periodo(n):
 i = 1;
 while ((10**i-1) % n) != 0:
  i = i+1;
 return i;
def facto(m):
 g = periodo (m);
 i = 1;
 k = mcd(m, 10**i-1);
 while k == 1:
  if g % i != 0:
   i = i+1;
  else:
   k = mcd(m, 10**i-1);
   i = i+1;
 print(k);
 print(m/k);

giovedì 10 aprile 2014

Equazione diofantina ax+by=c

ax+by= c     dati a, b, c trovare x, y

Z^2-cZ+abk=0   k = xy

Z = (c+sqrt(c^2-4abk))/2;
Z = (c-sqrt(c^2-4abk))/2;

quindi z < c^2 / 4ab

Z1 = ax => x
Z2 = by => y

c | MCD(a.b)

x = x*-cr/MCD(a, b)
y = y*-cr/MCD(a,b)
r= parametro intero
x*, y* soluzioni particolari

Osservazioni e note su alcuni algoritmi per RSA

x^2-sx+n=0
s = p+q
n= pq
x=p, q

p = (s+ sqrt(s^2-4n))/2
q = (s- sqrt(s^2-4n))/2

s >= 2sqrt(n)
p, q hanno lo stesso ordine di grandezza sono ovvero in genere composti dallo stesso numero di cifre

s^2-4n deve essere un quadrato perfetto, quindi l'ultima cifra deve essere tra queste: 0, 1, 4, 5, 6, 9

s deve essere pari perché somma di due dispari primi

inoltre è facile fare vedere che:
se n termina con 1 allora S deve terminare con 2 o 8 o 0
se n termina con 3 allora S deve terminare con 4 o 6
se n termina con 7 allora S  deve terminare con 2 o con 8
se n termina con 9 allora S deve terminare con 4 o 6 o 0

mentre considerando s/2 invece di s:
se n termina con 1 allora s/2 deve terminare con 1 o 6 o 4 o 9 o 0 o 5
se n termina con 3 allora s/2 deve terminare con 2 o 7 o 3 o 8
se n termina con 7 allora s/2 deve terminare con 1 o 6 o 4 o 9
se n termina con 9 allora s/2 deve terminare con 2 o 7 o 3 o 8 o 5 o 0

RSA una sfida possibile

giovedì 3 aprile 2014

Possibili attachi al sistema RSA: punti deboli della fattorizzazione


import math;
def facto(n):
 v = math.floor((n+1-2*math.sqrt(n))/4);
 s = n+1-4*v;
 delta = math.sqrt(s*s-4*n);
 while (delta != math.floor(delta)):
  v = v-1;
  s = n+1-4*v;
  delta = math.sqrt(s*s-4*n);
 p = (s+delta)/2;
 q = (s-delta)/2;
 print(p);
 print(q);


Equazioni diofantine risolte con EXCEL e i fogli di calcolo

Excel, Open Office, Libre Office, King soft Office, Gnumeric con il componente chiamato "risolutore delle equazioni" possono darci una mano a cercare le soluzioni alle più note equazioni diofantine: basta associare il problema della soluzione dell'equazione diofantina ad un problema di ricerca operativa dove la funzione obiettivo non è né di massimo né di minimo ma è proprio ,l'equazione stessa più i vincoli di interezza.

Possiamo allora cercare le soluzioni dell'ultimo teorema di fermat (insieme vuoto) o di altri noti problemi

provate anche con equazioni diofantine che hanno o non hanno soluzioni

Esempio (ultimo teorema di fermat: nessuna soluzione):
x^n+y^n-z^n = 0 (f. obiettivo)
vincoli
x, y, z >=1
n >2
x, y, z, n: integer