lunedì 18 settembre 2017

Mappa logistica con Mathematica

Ecco il codice in Mathematica applicabile a varie equazioni dei sistemi dinamici complessi

r = 4
x[0] = 0.8
x[_n]=r*x[n-1]*(1-x[n-1])
ParametricPlot[{t, x[t]}, {t, 0, 100}]



venerdì 8 settembre 2017

Probabilità e fattorizzazione

Estraendo un numero dispari a caso tra 1 la radice quadrata di n dove n = pq numero da fattorizzare , la probabilità di indovinare il fattore più piccolo è pari a :

P = 1/(sqrt(n)/2) = 2/sqrt(n) (considero solo i numeri dispari tra 1 la radice di n)

ovvero probabilità = numero di casi possibili / numero di caso totali

in realtà la formula precisa sarebbe

P = 1/((int(radq(n)/2)-1) ma non cambia molto il risultato

-int perché considero un numero intero di elementi,
-1 perché il numero lo escludo

ora

P = 1/(sqrt(n)/2-x) = 2/(sqrt(n)-2x) 

in realtà la formula precisa sarebbe

P = 1/(int(sqrt(n))/2-x-1) 

ci dà in modo approssimativo la probabilità di indovinare il fattore ( i numeri li possiamo estrarre senza ripetizione  con un generatore di numeri casuali) dopo aver estratto x numeri interi dispari minori della radice quadrata di n: probabilità che la prossima estrazione dia il risultato cercato.

Quindi risolvendo la disequazione in x

P = 1/(sqrt(n)/2-x) = 2/(sqrt(n)-2x)  > k  dove k è un valore di probabilità  0 < k < 1  troviamo quanti numeri dobbiamo estrarre per avere almeno una probabilità di k di trovare il fattore che stiamo cercando.

Il tempo da considerare sarà T = t*x dove t è il tempo necessario per effettuare un controllo (in sostanza una estrazione e una divisione)

Da questi elementi possiamo dedurre quanti numeri ci conviene di provare e il tempo impiegato per ottenere una discreta possibilità di successo.

Essendo però in numeri in gioco in enorme quantità si capisce presto che estrarre nuovi numeri cambia poco la probabilità di riuscire a fattorizzare un numero RSA






giovedì 7 settembre 2017

Calcolo dell'ordine moltiplicativo di a modulo n per fattorizzare i numeri RSA

sia dato a intero e primo con n, MCD(a,n)=1,
L'ordine moltiplicativo di a modulo n è il più piccolo valore i tale che
a^i =1 modulo n,
i = ord(a,n)

L'ordine moltiplicativo di a modulo n è molto importante perché divide la phi(n) e quindi può essere usato per fattorizzare n e per decrittare l'RSA
ord(a,n) | phi(n)

Quindi la phi(n) di un numero semi-primo, essendo phi(n)=(p-1)(q-1) con n = pq dove p, q sono primi deve essere phi(n) = k*ord(a,n) e deve essere la phi(n) un multiplo d 4

inoltre phi(n) < n-2*radq(n)+1

cercati i valori di phi(n) sappiamo che s = p+q = n-phi(n)+1
e troviamo p, q risolvendo l'equazione x^2-sx+n=0
finché non troviamo le soluzioni intere (se non le troviamo al primo tentativo valutiamo un altro valore per phi, quindi per s ecc)

ecco il codice per calcolarlo (in Python) per il calcolo dell'ordine moltiplicativo di a modulo n supponendo che MCD(a,n)=1

import math;
def ordine(a,n):
    i = math.floor(math.log(n)/(math.log(n)));
    c = (a**i)%n;
    while(c <> 1):
        i= i+1;
        c= (a**i)%n;
    print(i);

mercoledì 6 settembre 2017

Fattorizzazione semplice per RSA

x^2-sx+n=0

x1=p, x2 = q , n = pq

(p+q)+pq+1=(a+1)(b+1)=4k in quanto prodotto di due numeri pari essendo p, q primi quindi dispari

quindi

s+n+1=4k

ora s >= 2*radq(n)
quindi  k >=(n+1+2*radq(n))/4=((radq(n)+1)/2)^2

algoritmo
si sceglie k tale che

 k >=(n+1+2*radq(n))/4=((radq(n)+1)/2)^2

si calcola

s = 4k-n-1

e si trovano le radici di  x^2-sx+n=0

se sono entrambe intere: abbiamo trovato i fattori di n e abbiamo finito, altrimenti si passa al successivo intero valore di k


#include 
#include 
#include 

using namespace std;

int main(int argc, char *argv[])
{
    long int n, s;
    double  p, q;
    int k;
    long int i;
    cout << "inserisci il numero n " ;
    cin >> n;
    k = 1 + int((n+1+2*sqrt(n))/4);
    s = 4*k-n-1;
    p = (s+sqrt(s*s-4*n))/2;
    while(p != int(p))
    {
            k = k+1;
             s = 4*k-n-1;    
             p = (s+sqrt(s*s-4*n))/2;
            }
    q = n/p;
    cout << p << "\n";
    cout << q << "\n";

    system("PAUSE");
    return EXIT_SUCCESS;
}