Blum-Blum-Shub algoritem

Iz MaFiRaWiki

Vsebina

Blum-Blum-Shub generator

Blum-Blum-Shub generator (ali krajše BBS-generator) uporabljamo za generiranje psevdonaključnih števil. Leta 1986 so ga predlagali zakonca Lenore in Manuel Blum ter Michael Shub.

Kmalu po iznajdbi računalnika so ljudje začeli iskati učinkovite načine, kako generirati naključna števila z računalniškimi programi. Ker računalniki delujejo deterministično, imenujemo ta števila psevdonaključna števila. Psevdonaključna števila so zgenerirana po nekem vzorcu in jih je zelo težko ločiti od pravega naključnega števila.

Opis algoritma

  • Uporabnik izbere dve praštevili p in q, za kateri velja: p (mod 4) = q (mod 4) = 3. Če to velja, rečemo, da sta p in q Blumovi praštevili.
  • Število n je produkt števil p in q.
  • S pomočjo metode currentTimeMillis() generiramo naključno celo število s (seme), ki leži na intervalu [1,n-1] in za katerega je največjiSkupniVečkratnik(s,n)=1. Zelo pomembno je, da je seme dobro izbrano, saj je od tega odvisna varnost generatorja.
  • x0 = s2 (mod n)
  • stevilo = 0.0
  • Požene algoritem (za i = 1,2,...,dolzinaZaporedjaBitov) , ki sproti pretvarja dobljene bite v desetiški zapis:
    • izračuna naslednje število na podlagi prejšnjega: xi = xi-12 (mod n)
    • izračuna zi, ki je najmanjši pomemben bit števila xi: zi = xi (mod 2)
    • stevilo = stevilo + zi*2-i
  • Izhodni podatek je stevilo.

Uporaba

Naključna števila so uporabna v različnih situacijah: simulacije, vzorčenje, numerična analiza, računalniško programiranje, odločitveni problemi, estetika, rekreacija,..., posebej pomembna pa so naključna števila v kriptografiji, ki se ukvarja s kodiranjem sporočil. Naključna števila potrebujemo pri kodiranju e-mailov, digitalnih podpisih dokumentov, pri elektronskem plačilnem sistemu,... Ker jih je zelo težko zgenerirati, si pri tem pomagajo z generatorji psevdonaključnih števil, med katere spada tudi BBS-generator.

Implementacija v Javi

  1. public class BBS{
  2. public static double bbs(){
  3. int p = 11; // p,q Blumovi prastevili, za kateri je znacilno p(mod 4) = q(mod 4)= 3
  4. int q = 23;
  5. int n = p*q;
  6. int s;
  7. int st = 20; // dolzina psevdonakljucnega zaporedja bitov
  8. // s dolocimo glede na trenutni cas, ki je dolocen z milisekundami od 1.1.1970 naprej
  9. // lezi na intervalu [1,n-1] in za katerega velja, da je najvecjiSkupniVeckratnik(s,n)=1
  10. do {
  11. long ms = System.currentTimeMillis(); // število milisekund, ki so pretekle od 1.1.1970
  12. // ker je število ms tipa long in je veliko večje (max lahko 2^63-1) od največje cifre tipa int (2^31-1), dobimo s pretvorbo v int
  13. // negativno število, zato pomnožimo z -1
  14. s = (-1)*(int)ms%n;
  15. }while(gcd(s,n)!=1);
  16. double stevilo = 0.0;
  17. double stevec = 1;
  18. int pomozni;
  19. int bit;
  20. int x_0 = (s*s) % n; // x_0 določen s to formulo
  21. for (int i=1; i<=st; i++){
  22. pomozni = (x_0*x_0) % n; // racunamo naslednje x
  23. bit = pomozni%2; // dobimo bit (0 ali 1)
  24. stevec = stevec/2; // ker zelimo stevilo v desetiskem zapisu, na zacetku pomnozimo bit z 2^(-1), v naslednjem koraku z...
  25. stevilo = stevilo + bit *stevec; // ... 2^(-2), potem z 2^(-3) in tako naprej, v vsakem koraku dobljeno cifro pristejemo prejsnji
  26. x_0 = pomozni;
  27. }
  28. return stevilo;
  29. }
  30. // metoda, ki vrne najvecji skupni veckratnik dveh stevil
  31. public static int gcd(int m, int n){
  32. if (m < n){
  33. int t = m;
  34. m = n;
  35. n = t;
  36. }
  37. int r = m % n;
  38. if (r == 0) return n;
  39. else return gcd(n, r);
  40. }
  41. public static void main(String[] args){
  42. // izpisemo nastalo nakljuCno Stevilo
  43. System.out.println("Nakljucno stevilo je " +bbs() +".");
  44. }
  45. }

Primer

Kako deluje BBS-algoritem:

  • p in q določimo sami tako, da velja: p(mod 4) = q(mod 4)= 3 --> n = p*q = 11*23=253. S tem povečamo varnost generatorja.
  • s nam izračuna računalnik s pomočjo metode currentTimeMillis().
  • x0 = s*s(mod n), nadaljne xi dobimo po formuli xi = xi-12 (mod n), i = 1,2,...,dolzinaZaporedjaBitov
  • zi = xi(mod 2), i = 1,2,...,dolzinaZaporedjaBitov
  • stevilo = 0.0
x0 = 1002(mod 253) = 133
x1 = 1332(mod 253) = 232 --> z1 = 232 % 2 = 0 --> stevilo = 0.0 + 0*(2-1) = 0
x2 = 2322(mod 253) = 188 --> z2 = 188 % 2 = 0 --> stevilo = 0.0 + 0*(2-2) = 0
x3 = 1882(mod 253) = 177 --> z3 = 177 % 2 = 1 --> stevilo = 0.0 + 1*(2-3) = 0.125
x4 = 1772(mod 253) = 210 --> z4 = 210 % 2 = 0 --> stevilo = 0.125 + 0*(2-4) = 0.125
x5 = 2102(mod 253) = 78 --> z5 = 78 % 2 = 0 --> stevilo = 0.125 + 0*(2-5) = 0.125

Izhodni podatek je število 0.125.

Osebna orodja