giovedì 16 gennaio 2014

Ancora sulle successioni di Fibonacci per la fattorizzazione

algoritmo:
si voglia fattorizzare N =pq con p, q numeri primi

F(0) = a (a numero qualunque a < N )
F(1) = N
F(m)=F(m-1)+F(m-2) m = 2, 3, 4, ......
finché
MCD(F(m), N) != 1 allora MCD(F(m), N) = p oppure MCD(F(m), N) = q

La programmazione In Python risulta molto semplice

oppure: (serie di F. generalizzate)
F(0) = a (a numero qualunque a < N )
F(1) = b (a numero qualunque a < N )
F(m)=F(m-1)+F(m-2) m = 2, 3, 4, ......
finché
MCD(F(m), N) != 1 allora MCD(F(m), N) = p oppure MCD(F(m), N) = q

CASO 1)
def fib(m, a, b):
 if m == 0 :
  return a;
 elif m == 1:
  return b;
 else:
  return fib(m-1, a, b)+fib(m-2, a, b);

def mcd(a, b):
 if b == 0:
  return a;
 else:
  return mcd(b, a%b);
def factor(n, b):
 a = n;
 j = 2;
 while(mcd(fib(j, a, b), n)== 1): //oppure  while(c=mcd(fib(j, a, b), n)== 1)
  j = j+1;
 c = mcd(fib(j, a, b), n);
 d = n/c;
 print(c);
 print(d);

CASO 2) successioni generalizzate per a=b=1 serie di Fibonacci
def fib(m, a, b):
 if m == 0 :
  return a;
 elif m == 1:
  return b;
 else:
  return fib(m-1, a, b)+fib(m-2, a, b);

def mcd(a, b):
 if b == 0:
  return a;
 else:
  return mcd(b, a%b);
def factor(n, a, b):
 j = 2;
 while(mcd(fib(j, a, b), n)== 1): //oppure  while(c=mcd(fib(j, a, b), n)== 1)
  j = j+1;
 c = mcd(fib(j, a, b), n);
 d = n/c;
 print(c);
 print(d);

martedì 7 gennaio 2014

Crittografia simmetrica: costruzione della chiave comune

Codice sorgente in VB per realizzare un software che consente di generare una password comune supponendo di trasmettere i valori di x in un canale insicuro e che y=f(x) mod n sia una funzione nota solo ad A, oppure a B ma a nessun altro. Per comunicare con altri soggetti si dovrà comunque cambiare la y=f(x)

Module Module1

    Sub Main()
        Dim car As Char
        Dim max As Integer
        Dim i As Integer
        Dim s As String
        Dim y As Integer
        Dim x As Integer
        s = ""
        Console.WriteLine("quanti caratteri ?")
        max = Console.ReadLine()
        For i = 0 To max - 1
            Console.WriteLine("insrisci codice numerico")
            x = Console.ReadLine()
            y = Math.Pow(x, 3) - 3 * Math.Pow(x, 2) + 24 * x + 7
            y = y - 256 * Int(y / 256)
            car = Chr(y)
            s = s & car
        Next
        Console.WriteLine("ecco la password. fai copia e incolla")
        Console.WriteLine(s)
        Console.WriteLine("inserisci un carattere per terminare")
        Console.ReadLine()
    End Sub

End Module

sabato 4 gennaio 2014

RSA: attacco con algoritmi paralleli

Da x^2-Sx+W=0 con W = pqk, S=q+kp, n=pq, x=q, kp otteniamo il seguente algoritmoin Python (dove ogni PC avrà un differente valore di k intero):

import math;
def mcd(a,b):
        if b ==0:
            return a;
        else:
            return mcd(b, a%b);
def facto1(n, k):
 s = 2*math.floor(math.sqrt(n*k));
 if (k/2 == math.floor(k/2)):
  a = 1;
 else:
  a = 2;
 p = (s-math.sqrt(math.fabs(s*s-4*n*k)))/2;
 while (p != math.floor(p)):
  s = s+a;
  p = (s-math.sqrt(math.fabs(s*s-4*n*k)))/2;
 c = mcd(p, n);
 print(n/c);
 print(c);

venerdì 3 gennaio 2014

privacy e hash

Hash a difesa della privacy dello studente. Supponiamo che un docente invece di pubblicare i nomi e i cognomi degli studenti che hanno sostenuto un certo esame pubblichi l'hash della stringa "cognome[spazio]nome[spazio]matricola" accanto al voto finale dove il cognome e il nome sono scritti in maiuscolo. I nominativi degli studenti sarebbero quindi criptati (dall'hash non si può risalire alla stringa che lo ha generato e due stringhe differenti generano sempre hash differenti). Lo studente che vuole sapere il risultato del suo esame prima calcola l'hash del suo cognome + spazio + nome+ spazio+matricola poi verifica se l'hash se è presente nell'elenco e quindi il voto riportato che è invece in chiaro.Al posto della matricola possiamo mettere il codice fiscale del soggetto. Con questo esempio si tutela la privacy. L'hash si potrebbe calcolare in base all'sha2 a 256 bit. Le applicazioni che tutelano la privacy con l'hash potrebbero non finire qui (ad esempio la gestione degli account nome_utente, password di un servizio on line, la tutela dei nominativi di un albergo ecc)

mercoledì 1 gennaio 2014

Algoritmo specializzato per numeri RSA

da n=pq, q =kp+a , oppure q=kp-a deduciamo facilmente i seguenti algoritmi in Python

caso k dispari k = 1, 3, 5, 7, 9 per numeri RSA

import math;
def factor(n, k):
 a = 2;
 p = (-a+math.sqrt(a*a+4*n*k))/(2*k);
 while (p != math.floor(p)):
  a = a-2;
  p = (-a+math.sqrt(a*a+4*n*k))/(2*k);
 q = n/p;
 print(p);
 print(q);

-----
caso k dispari k = 1, 3, 5, 7, 9 per numeri RSA

import math;
def factor(n, k):
 a = 2;
 p = (a+math.sqrt(a*a+4*n*k))/(2*k);
 while (p != math.floor(p)):
  a = a+2;
  p = (a+math.sqrt(a*a+4*n*k))/(2*k);
 q = n/p;
 print(p);
 print(q);
-------
caso k dispari k = 1, 3, 5, 7, 9 per numeri RSA

import math;
def factor(n, k):
 a = 2;
 p = (a-math.sqrt(a*a+4*n*k))/(2*k);
 while (p != math.floor(p)):
  a = a-2;
  p = (a-math.sqrt(a*a+4*n*k))/(2*k);
 q = n/p;
 print(p);
 print(q);
---------------------
caso: k pari k = 0, 2, 4, 6, 8, .... per numeri RSA

import math;
def factor(n, k):
 a = 1;
 p = (a+math.sqrt(a*a+4*n*k))/(2*k);
 while (p != math.floor(p)):
  a = a+2;
  p = (a+math.sqrt(a*a+4*n*k))/(2*k);
 q = n/p;
 print(p);
 print(q);
-----------------
caso: k pari k = 0, 2, 4, 6, 8, .... per numeri RSA

import math;
def factor(n, k):
 a = 1;
 p = (a-math.sqrt(a*a+4*n*k))/(2*k);
 while (p != math.floor(p)):
  a = a-2;
  p = (a-math.sqrt(a*a+4*n*k))/(2*k);
 q = n/p;
 print(p);
 print(q);