Pagine    Articoli    Prodotti    Forum    Cerca  
Nickname

Password


Non sei registrato?
Registrati a GPI qui!

Puoi anche attivare un vecchio utente GPI e chiedere una nuova password.
I Team

Mappa Team
I nostri utenti

Mappa Utenti
  RSA: Creare numeri primi per la crittografia
Pubblicato da Dario Oliveri il 2014-02-19 14:09:23

Perchè questo articolo? Semplice: Siamo realmente sicuri che chi crea numeri primi per noi non ne tenga traccia in qualche modo o crei appositamente chiavi crittografiche deboli (usando magari lo stesso numero primo in più chiavi, in modo che queste diventino fattorizzabili con Euclide), in modo che per ragioni governative o meno lecite (o semplicemente per colpa della non-curanza) un qualche ente con sufficiente potenza di calcolo possa a piacimento decriptare i nostri dati sensibili?

 

Per generare una chiave pubblica e una chiave privata per la crittografia RSA sono necessari 2 numeri primi molto grandi (più grandi sono meglio è).

 

DISCLAIMER: non c'è alcuna garanzia che sia effettivamente sicuro usare il codice proposto in questo articolo. Lo fate a vostro rischio e pericolo

 

 

Materiale necessario:

-Una libreria per gestire numeri interi grandi (per il C++ "C++ Big Integer Library").

 

-Algoritmo di Euclide (vecchio di migliaia di anni! anzi forse era noto già ben prima di Euclide, per nostra fortuna è già nella libreria sotto forma della funzione "gcd" ovvero "Massimo Comun Divisore")

 

Matematica Necessaria

 

1)-Numeri coprimi:

2 numeri sono coprimi, se il loro MCD (Massimo Comun Divisore) è 1. Per trovare il MCD di due numeri bisogna usare l'algoritmo di Euclide.

 

La probabilità che due numeri interi (scelti a caso) siano coprimi è 6/(PI^2).

  fonte: Wikipedia

 

2)-Numero Primo:

Un numero primo è coprimo con tutti i suoi predecessori.

 

La probabilità che un intero N (scelto a caso) sia un numero primo è 1/logN.

  fonte: Wikipedia

 

In pratica la matematica ci dice che 2) preso un numero qualunque, c'è probabilmente un numero primo nei suoi dintorni.

 

Se ad esempio prendiamo il numero 10^1000, ovvero un numero di 1000 cifre, sappiamo che ha una probabilità di 1/1000 di essere un numero primo, lo stesso vale anche per i numeri che stanno prima e dopo di lui, è molto improbabile quindi che non ci sia un numero primo compreso tra 10^1000+1000 e 10^1000-1000.

 

Sappiamo quindi che se cerchiamo un numero primo è abbastanza facile trovarlo, ma come facciamo a riconoscerlo?

 

Ci serve un test di primalità.

 

In realtà esistono test molto raffinati, quello che vi propongo in questo articolo è abbastanza "grossolano", ma è per darvi un idea e permettere anche a noi comuni mortali di toccare i numeri primi :D.

 

Algoritmo:


Prendo un numero intero casuale P abbastanza grande, provo a fare il Massimo Comun Divisore con almeno K altri interi casuali abbastanza grandi. Se il risultato è sempre 1, con molta probabilità (non c'è alcuna certezza) abbiamo trovato un numero primo. Se il risultato è diverso da 1, siamo certi che non è un numero primo e possiamo provare con un altro numero, in particolare ci conviene provare ad usare P++.

 

Possiamo ripetere il procedimento fino a quando ci stufiamo (perchè abbiamo avuto sfortuna e non abbiamo trovato numeri potenzialmente primi) oppure possiamo continuare fino a quando non troviamo un numero primo.

 

Ecco il codice, ma con vari avvertimenti:

 

1)Per fare prima ho usato la funzione di libreria C  "rand" che in realtà non è casuale anzi spesso e volentieri si comporta in modo non casuale.

2)le cifre sono inserite al contrario.. Se quindi voi digitate "594832" il numero di partenza che avete creato è in realtà "238495". (per mia comodità :P )

 

#include "BigIntegerLibrary.hh"
#include < iostream >
#include < cstdlib >

/** Compone il numero partendo dalle cifre decimali inserite dall'utente.*/
void chiediNumero(BigUnsigned & target, int digits){
    std::cout < < "Inserire " < < digits < < " cifre decimali"  < < std::endl;
    target = 0;
    BigUnsigned k = 1;
    while(digits > 0){
        char c;
        std::cin > > c;
        switch(c){
            case '1': target += (k); break;
            case '2': target += (k*2); break;
            case '3': target += (k*3); break;
            case '4': target += (k*4); break;
            case '5': target += (k*5); break;
            case '6': target += (k*6); break;
            case '7': target += (k*7); break;
            case '8': target += (k*8); break;
            case '9': target += (k*9); break;
            default: break;
        }
        k*=10;
        digits--;
    }
}

/**E' disumano chiedere all'utente di inserire 2048*1000 cifre XD.*/
void numeroCasuale(BigUnsigned & target, int digits){
    target = 0;
    BigUnsigned k = 1;
    while(digits > 0){
        int c = std::rand()%10;
        target += (k*c);
        k*=10;
        digits--;
    }
}

/** Chiede il numero di cifre decimali all'utente*/
int chiediCifre(){
    using namespace std;
    cout < < "Inserisci il numero di cifre decimali:\n" < < endl;
    int a;
    cin > > a;

    if(a < 10)
        a = 10;
    if(a > 1000)
        a = 1000;

    return a;
}

int main(){
    using namespace std;
    int cifre = chiediCifre();
    cout < < cifre  < < endl;
    BigUnsigned P = 0;
    chiediNumero(P,cifre);
    cout < < "Calcolo in corso.." < < endl;

    const double PI = 3.1416;
    const double f = 6.0 / (PI*PI);
    const double p = 1.0 /(double)(cifre+2); //+2 tanto per stare sicuri.

    int k=1;
    double f2 = f;
    while(-log10(f2) < cifre && f2 < (p*cifre*cifre)){ //a meno di raggiungere i limiti di double... termina ^^
        k*=2;
        f2*=f2;
    }
    cout < < "Devono essere inseriti almeno " < < k < < " numeri" < < endl;
    // SE SIETE DUBBIOSI DELL'ALGORITMO A QUESTO PUNTO POTETE AUMENTARE "k"
    // DI QUANTO VOLETE (nei limiti della memoria del vostro computer XD)

    BigUnsigned * dividendi = new BigUnsigned[k];
    for(int i = 0; i < k; i++){
        dividendi[i] = 0;
        numeroCasuale(dividendi[i],cifre-2);
    }

    BigUnsigned One = 1;
    cout < < "Calcolo primalita':" < < endl;
    for(int i=0; i < (cifre*9); i++){
        for(int j = 0; j < k; j++){
            if( gcd(P,dividendi[j])!=One){
                cout < < " P + "  < < i < < " (" < < i < < "/" < < cifre*9 < < ") non e' primo.. skipping" < < endl;
                break;
            }

            if (j+1==k){
                cout < < " P + "  < < i < < " (" < < i < < "/" < < cifre*9 < < ") e' probabilmente un numero primo.." < < endl;
                cout < < "Ecco quanto vale P + " < < i < < " :" < < endl;
                cout < < P;
                return 0;
            }
        }
        P+=1;
    }

    delete [] dividendi;
    return 0;
}

 

 

 

 

Se ad esempio usiamo un numero di 50 cifre come input dell'algoritmo:

 

57538098756431628569086537653462314678935416789453

 

che al contrario diventa

 

35498761453987641326435673568096582613465789083575

 

il programma trova che probabilmente

 

35498761453987641326435673568096582613465789083583

 

è un numero primo.

 

 

 

Un esempio di numero probabilmente primo con 500 cifre decimali (2 minuti di calcolo necessari):

55176322038975477562948376507060702948413861284659454005760135004307046222153523
11234357927302528303787703924444475218578824369504439294630519264126816352823553
36161445285667539679976939380521945528969149227768525235918193002592679112816429
35626852421685187098282279891860880834733355299484386990156943701738387780889341
48981604610215387490521083066281899533777717064100214575610627379024516367048953
19288736948166064439831600905684206820568913977247831143321345972981675861223241
67251171554288490483

 

Un esempio di numero probabilmente primo con 1000 cifre decimali (10 minuti di calcolo necessari, è normale che questi 2 numeri terminino con le stesse identiche cifre, non preoccupatevi. Dipende semplicemente dal fatto che per prigrizia li ho generati con la funzione "rand" usando lo stesso seme iniziale, non avevo voglia di inserire 1000 cifre a mano XD):

96063980965853731451084833018396278380951150440542829055574108979539184107829835
24153198989132043289129363415088008937486343432826334200671510155286264416653526
54936628623524546915516854679384938565367800390684810828193973873855907331307222
31088505495929862553418478239550284139240910363134770865478092142335714309177169
72859314529584014350970580195227082530363284712255130182563647431980354601595114
23858751373297244423562959931567272619177676665302654105438001738747039807758830
92103840037111606204551763220389754775629483765070607029484138612846594540057601
35004307046222153523112343579273025283037877039244444752185788243695044392946305
19264126816352823553361614452856675396799769393805219455289691492277685252359181
93002592679112816429356268524216851870982822798918608808347333552994843869901569
43701738387780889341489816046102153874905210830662818995337777170641002145756106
27379024516367048953192887369481660644398316009056842068205689139772478311433213
4597298167586122324167251171554288490483

 

Campagne crowfunding

Just One Line
Siamo presenti su

     
Copyright ©2016 - Manifesto - Privacy - Termini di Servizio - Community - Collaboratori - Contattaci