mercoledì 27 novembre 2013

Equazioni diofantine e numeri complessi


Potenze e fattorizzazione RSA

ALGORITMO DELLE POTENZE GENERALIZZATO PER RSA (c è a piacere)
import math;
def mcd(a, b):
 if  b == 0:
  return a;
 else:
  return mcd(b, a%b);

def facto(n, C):
 M = 1
 while (math.pow(C,M) <= n):
  M = M+1;
 i = 3;
 while (mcd(math.pow(C,M)-i, n)==1):
  i = i+2;
 p = mcd(math.pow(C, M)-i, n);
 q = n/p;
 print(p);
 print(q);


lunedì 25 novembre 2013

Fattoriali e potenze: algoritmi veloci per problemi RSA

ALGORITMO DI FATTORIZZAZIONE CON FATTORIALI
import math;
def mcd(a, b):
 if  b == 0:
  return a;
 else:
  return mcd(b, a%b);
def fattoriale(x):
 if x < 2:
  return 1;
 else:
  return x*fattoriale(x-1);
def facto(n):
 M = 1
 while (fattoriale(M) <= n):
  M = M+1;
 i = 3;
 while (mcd(fattoriale(M)-i, n)==1):
  i = i+2;
 p = mcd(fattoriale(M)-i, n);
 q = n/p;
 print(p);
 print(q);

-----------------------------------
ALGORITMO DI FATTORIZZAZIONE CON POTENZE
import math;
def mcd(a, b):
 if  b == 0:
  return a;
 else:
  return mcd(b, a%b);

def facto(n):
 M = 1
 while (math.pow(2,M) <= n):
  M = M+1;
 i = 3;
 while (mcd(math.pow(2,M)-i, n)==1):
  i = i+2;
 p = mcd(math.pow(2, M)-i, n);
 q = n/p;
 print(p);
 print(q);
------------------------------------------------
ALGORITMO DI FATORIZZAZIONE CON EQUAZIONE DI II GRADO
import math;
def mcd(a,b):
 if b == 0:
  return a;
 else:
  return mcd(b, a%b);
def fact(n, l):
 l = 2*l+1;
 w = 2;
 while(math.floor(math.sqrt(l*l+4*w*n)) != math.sqrt(l*l+4*w*n)):
  w = w+2;
 m = mcd(w, (-l+math.sqrt(l*l+4*w*n))/2);
 q = (-l+math.sqrt(l*l+4*w*n))/(2*m);
 p = n/q;
 print(p);
 print(q);

domenica 10 novembre 2013

Relazione tra fattorizzazione dei numeri RSA e terne pitagoriche

s= p+q
n = pq
d = p-q


s^2 = 4n +d^2

n = [(s-d)/2]^2 + [(s+d)/2]^2


k = k*1 = [(k-1)/2]^2 +[(k+1)/2]^2
(ogni numero k dispari, quindi anche ogni numero primo, può essere espresso come differenza di due quadrati e se è primo in maniera unica altrimenti in maniera non unica).

k = M^2

M^2 = [(M^2-1)/2]^2 +[(M^2+1)/2]^2 (terne pitagoriche)

da s^2 = 4n +d^2
ponendo n = P^2 *  Q^2 abbiamo

[P^2+Q^2]^2 = [2PQ]^2 + [P^2-Q^2]^2 (f.generale delle t.pitagoriche)

giovedì 7 novembre 2013

Sistema di protezione e di identificazione

Ecco la descrizione di un sistema di protezione con nome utente e password 
1) l'utente inserisce a = nome utente
2) il sistema memorizza solo l'hash del nome utente h1=hash(a)
3) l'utente inserisce la password = passw
4) il sistema memorizza solo l'hash della password h2 = hash(passw)
5) il sistema unisce i due hash h = h1 h2
6) il sistema controlla se nell'archivio delle persone autorizzare esiste h: se sì si procede altrimenti no

In questo modo il sistema controlla gli accessi ma non registra le username e le password degli utenti ma li identifica in maniera sicura

Note 1) essendo un hash da h1 e/o da h2 non si può risalire al nome utente a alla password e non è possibile che due utenti abbiano lo stesso hash finale h2.

Module Module1

    Sub Main()
        Dim user As String
        Dim pass As String
        Dim hash As String
        Dim hash1 As String
        Console.WriteLine("--------------------")
        Console.WriteLine("registrazione utente")
        Console.WriteLine("inserisci il nome utente")

        user = Console.ReadLine().GetHashCode.ToString
        Console.WriteLine("inserisci password")
        pass = Console.ReadLine().GetHashCode.ToString

        hash = user + pass
        user = ""
        pass = ""
        Console.WriteLine("ti sei registrato")
        Console.WriteLine("--------------------")

        Console.WriteLine("inserisci il nome utente")
        user = Console.ReadLine().GetHashCode.ToString
        Console.WriteLine("inserisci password")
        pass = Console.ReadLine().GetHashCode.ToString
        hash1 = user + pass

        If (hash1 = hash) Then
            Console.WriteLine("sei tu")
        Else
            Console.WriteLine("errore")
        End If
        Console.ReadLine()

    End Sub
End Module