| dbo:abstract
|
- Blum Blum Shub (BBS) je jednoduchý generátor pseudonáhodných čísel z třídy (CSPRNG). Název je odvozen od autorů, kteří popsali v roce 1986 (resp. 1982) jeho vlastnosti. Těmi jsou , Manuel Blum a . BBS používá rekurzivní formuli xi = (xi-1)2 mod M kde
* M je součin dvou velkých (tajných) prvočísel p a q, pro ta by mělo platit, že jsou
* kongruentní 3 modulo 4
* stejné délky
* x0 je inicializační hodnota (seed), splňující
* 0 < x0 < M
* gcd(x0, M) = 1
* výstupem generátoru je bit získaný jako bitová parita čísla xi Výhodou generátoru je možnost přímo vypočítat xi: xi = x2i mod λ(M)0 mod M kde λ je Carmichaelova funkce. Blum Blum Shub je zajímavý spíše z teoretického hlediska a v praxi se příliš nepoužívá, kvůli malé rychlosti a nutnosti utajení p a q. (cs)
- Der Blum-Blum-Shub-Generator (BBS-Generator) ist ein Pseudozufallszahlengenerator, entwickelt 1986 von Lenore Blum, Manuel Blum und Michael Shub. Anwendung findet das System u. a. in der Kryptologie im Entwurf komplexitätstheoretisch sicherer Kryptosysteme. (de)
- Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub that is derived from Michael O. Rabin's one-way function. (en)
- Blum Blum Shub (BBS) es un generador pseudoaleatorio de números propuesto por Lenore Blum, Manuel Blum y en 1986. El algoritmo BBS es: xn+1 = (xn)2 mod M donde M=pq es el producto de dos números primos muy grandes p y q. En cada paso del algoritmo, se obtiene un resultado para xn; el resultado es por lo general o bien el bit de paridad de xn ó uno o más de los bits menos significativos de xn. Los dos números primos, p y q, deben ser ambos congruentes a 3 (mod 4) (esto asegura que cada residuo cuadrático posee una raíz cuadrada que también es un residuo cuadrático) y mcd(φ(p-1), φ(q-1)) debe ser pequeña (esto hace que la longitud del ciclo sea extensa). Una característica interesante del generador BBS es la posibilidad de calcular todo valor xi en forma directa: (es)
- Blum Blum Shub (BBS) est un algorithme capable de produire des nombres pseudo-aléatoires. Il fut proposé en 1986 par Lenore Blum, Manuel Blum et Michael Shub, d'où son nom. (fr)
- Blum-Blum-Shub（B.B.S.）は、マヌエル・ブラムとLenore BlumとMichael Shubが提案した暗号論的擬似乱数生成器である。1986年に発表された (Blum et al, 1986)。 漸化式は次のような形をしている。 xn+1 = (xn)2 mod M ここで M=pq は2つの素数 p と q の積である。アルゴリズムの各ステップにおいて、xn から何らかの出力が得られる。この出力は一般に xn のビットパリティを使うか、または xn の1ビット以上の最下位ビット列を使う。 2つの素数 p と q は共に、(mod 4 で）3 と合同で（このとき、それぞれの平方剰余数の4つの平方根のうち、平方剰余であるものがちょうど一つである）、かつ gcd(φ(p-1), φ(q-1)) が小さいのが望ましい（これにより、反復周期が長くなる）。 Blum-Blum-Shub の興味深い性質として、任意の xi の値を次のように直接計算することができる。 (ja)
- L'algoritmo Blum Blum Shub (BBS) è un generatore di numeri pseudo-casuali crittograficamente sicuro proposto nel 1986 da , Manuel Blum e . L'algoritmo è il seguente: 1.
* Si generino due numeri primi casuali segreti p e q di molti bit, entrambi congruenti a 3 modulo 4 (cioè divisi per 4 danno resto 3) e si calcoli l'intero di Blum n =p·q 2.
* Si generi un numero casuale s (detto seme) appartenente all'intervallo [1, n-1] e coprimo rispetto a n. Si calcoli x0 ← s2 mod n 3.
* Per i che va da 1 a l (con l pari al numero di bit casuali che si vogliono generare) si eseguano i seguenti passi: 4. 1.
* xi ← xi -12 mod n 5. 2.
* zi ← bit meno significativo di xi 6.
* Il risultato dell'algoritmo è la sequenza di bit z1, z2, ..., zl, Il fatto che p e q siano congruenti a 3 modulo 4 garantisce che il MCD(φ(p -1), φ(q -1)) sia piccolo (il che rende più lungo il ciclo per cui xi torna ad essere uguale a x0). (it)
- Blum Blum Shub – generator liczb pseudolosowych (PRNG) postaci: gdzie to kolejne stany, a to iloczyn dwóch dużych liczb pierwszych i dających w dzieleniu przez 4 resztę 3 (dzięki czemu każda reszta kwadratowa modulo ma jeden pierwiastek kwadratowy, który także jest resztą kwadratową), i mających możliwie mały a jest funkcją Eulera (co zapewnia długi cykl). Wynikiem generatora jest kilka ostatnich bitów Generator ten jest dość powolny, za to bardzo bezpieczny. Przy odpowiednich założeniach, odróżnienie jego wyników od szumu jest równie trudne jak faktoryzacja tak więc jest stosowany głównie w kryptografii. Może się zdarzyć, że znaleziony zostanie szybki algorytm faktoryzacji i Blum Blum Shub przestanie być bezpieczny. Algorytm został po raz pierwszy opisany w pracy: L. Blum, M. Blum, M. Shub, A Simple Unpredictable Pseudo-Random Number Generator, „SIAM Journal on Computing”, vol. 15, s. 364–383, May 1986. (pl)
- Blum Blum Shub (BBS) é um gerador de números pseudoaleatórios proposto por Lenore Blum, Manuel Blum e Michael Shub em 1986. O algoritmo BBS é: xn+1 = (xn)² mod M onde M=pq é o produto de dois números primos muito grandes p e q. Em cada passo do algoritmo, obtém-se um resultado para xn; o resultado é geralmente o bit de paridade de xn ou um ou mais dos bits menos significativos de xn. Os dois números primos, p e q, devem ser ambos congruentes a 3 (mod 4) (isto assegura que cada resíduo quadrático tenha uma raiz quadrada que também é um resíduo quadrático) e mdc (φ(p-1), φ(q-1)) deve ser pequena (isto faz que o comprimento do ciclo seja extenso). Uma característica interessante do gerador BBS é a possibilidade de calcular todo o valor xi de forma directa: (pt)
- Алгоритм Блюм — Блюма — Шуба (англ. Algorithm Blum — Blum — Shub, BBS) — генератор псевдослучайных чисел, предложенный в 1986 году Ленор Блюм, Мануэлем Блюмом и . BBS выглядит так: где является произведением двух больших простых и . На каждом шаге алгоритма выходные данные получаются из путём взятия либо бита чётности, либо одного или больше наименее значимых бит . Два простых числа, и , должны быть оба сравнимы с 3 по модулю 4 (это гарантирует, что каждый квадратичный вычет имеет один квадратный корень, который также является квадратичным вычетом) и наибольший общий делитель НОД должен быть мал (это увеличивает длину цикла). Интересной особенностью этого алгоритма является то, что для получения необязательно вычислять все предыдущих чисел, если известно начальное состояние генератора и числа и . -ное значение может быть вычислено «напрямую» используя формулу: , где — функция Кармайкла: в данном случае — наименьшее общее кратное чисел и . (ru)
- Blum Blum Shub (B.B.S.) är en pseudoslumptalsgenerator (PSTG) och är även kryptologiskt säker. B.B.S. har formen: . där utsignalen ofta presenteras som pariteten för xi , på formen z1, z2, … zi. Alla de log (log (M)) första bitarna är dock säkra att använda. Startvärdet x0 räknas fram genom formeln x0 = s2 (mod M), där s ska vara ett tal mellan 1 och M-1, tillhöra de naturliga talen och p och q ska inte vara en faktor i s. M är produkten mellan två unika tillräckligt stora p och q (M = pq), där p och q uppfyller: . Denna egenskap gör att varje xi (som är en kvadratisk rest) enbart har en rot som är en kvadratisk rest, vilket gör det möjligt (om man känner till p och q) att ta fram xi-1 entydigt. För att få en så lång cykellängd som möjligt så ska SGD(φ(p-1), φ(q-1)) vara så liten som möjligt (där φ(n) är Eulers fi-funktion). För att räkna ut cykellängden, d.v.s. hur många iterationer som måste köras innan dess att talen upprepar sig (x0 = xlängd), använder man formeln λ(λ (M)) = längd, där lambda är . Detta gäller oftast men endast med säkerhet då ytterligare ett krav ställs på valet av p och q, samt att s måste väljas mer specifikt. En intressant egenskap hos B.B.S. är att det är möjligt att räkna fram xi för alla i via Eulers sats: . Om man känner till x0 samt M, vilket också gör det möjligt att räkna sekvensen framåt. Genom att känna till xi+1 och faktorerna i M d.v.s. p och q kan man även räkna sekvensen baklänges. (sv)
- Алгоритм Блум - Блум - Шуба (англ. Algorithm Blum — Blum — Shub, BBS) - генератор псевдовипадкових чисел, запропонований в 1986 році , Мануелем Блумом і . BBS має такий вигляд: де є добуток двох великих простих чисел і . На кожному кроці алгоритму вихідні дані обчислюють з шляхом взяття або біта парності, або одного чи більше найменш значущих бітів . Два простих числа, і , повинні бути конгруентні з 3 по (це гарантує, що кожен квадратний залишок має один квадратний корінь, який також є квадратним залишком) і найбільший спільний дільник НСД має бути маленьким (це збільшує довжину циклу). Цікавою особливістю цього алгоритму є те, що для отримання необов'язково обчислювати всі попередні числа, якщо відомо початковий стан генератора і числа і . - е значення може бути обчислено безпосередньо використовуючи формулу: , де - функція Кармайкла: в даному випадку - найменше спільне кратне чисел і. (uk)
|
| rdfs:comment
|
- Der Blum-Blum-Shub-Generator (BBS-Generator) ist ein Pseudozufallszahlengenerator, entwickelt 1986 von Lenore Blum, Manuel Blum und Michael Shub. Anwendung findet das System u. a. in der Kryptologie im Entwurf komplexitätstheoretisch sicherer Kryptosysteme. (de)
- Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub that is derived from Michael O. Rabin's one-way function. (en)
- Blum Blum Shub (BBS) est un algorithme capable de produire des nombres pseudo-aléatoires. Il fut proposé en 1986 par Lenore Blum, Manuel Blum et Michael Shub, d'où son nom. (fr)
- Blum-Blum-Shub（B.B.S.）は、マヌエル・ブラムとLenore BlumとMichael Shubが提案した暗号論的擬似乱数生成器である。1986年に発表された (Blum et al, 1986)。 漸化式は次のような形をしている。 xn+1 = (xn)2 mod M ここで M=pq は2つの素数 p と q の積である。アルゴリズムの各ステップにおいて、xn から何らかの出力が得られる。この出力は一般に xn のビットパリティを使うか、または xn の1ビット以上の最下位ビット列を使う。 2つの素数 p と q は共に、(mod 4 で）3 と合同で（このとき、それぞれの平方剰余数の4つの平方根のうち、平方剰余であるものがちょうど一つである）、かつ gcd(φ(p-1), φ(q-1)) が小さいのが望ましい（これにより、反復周期が長くなる）。 Blum-Blum-Shub の興味深い性質として、任意の xi の値を次のように直接計算することができる。 (ja)
- Blum Blum Shub (BBS) je jednoduchý generátor pseudonáhodných čísel z třídy (CSPRNG). Název je odvozen od autorů, kteří popsali v roce 1986 (resp. 1982) jeho vlastnosti. Těmi jsou , Manuel Blum a . BBS používá rekurzivní formuli xi = (xi-1)2 mod M kde
* M je součin dvou velkých (tajných) prvočísel p a q, pro ta by mělo platit, že jsou
* kongruentní 3 modulo 4
* stejné délky
* x0 je inicializační hodnota (seed), splňující
* 0 < x0 < M
* gcd(x0, M) = 1
* výstupem generátoru je bit získaný jako bitová parita čísla xi Výhodou generátoru je možnost přímo vypočítat xi: xi = x2i mod λ(M)0 mod M (cs)
- Blum Blum Shub (BBS) es un generador pseudoaleatorio de números propuesto por Lenore Blum, Manuel Blum y en 1986. El algoritmo BBS es: xn+1 = (xn)2 mod M donde M=pq es el producto de dos números primos muy grandes p y q. En cada paso del algoritmo, se obtiene un resultado para xn; el resultado es por lo general o bien el bit de paridad de xn ó uno o más de los bits menos significativos de xn. Una característica interesante del generador BBS es la posibilidad de calcular todo valor xi en forma directa: (es)
- L'algoritmo Blum Blum Shub (BBS) è un generatore di numeri pseudo-casuali crittograficamente sicuro proposto nel 1986 da , Manuel Blum e . L'algoritmo è il seguente: 1.
* Si generino due numeri primi casuali segreti p e q di molti bit, entrambi congruenti a 3 modulo 4 (cioè divisi per 4 danno resto 3) e si calcoli l'intero di Blum n =p·q 2.
* Si generi un numero casuale s (detto seme) appartenente all'intervallo [1, n-1] e coprimo rispetto a n. Si calcoli x0 ← s2 mod n 3.
* Per i che va da 1 a l (con l pari al numero di bit casuali che si vogliono generare) si eseguano i seguenti passi: 4. 1.
* xi ← xi -12 mod n 5. 2.
* zi ← bit meno significativo di xi 6.
* Il risultato dell'algoritmo è la sequenza di bit z1, z2, ..., zl, (it)
- Blum Blum Shub – generator liczb pseudolosowych (PRNG) postaci: gdzie to kolejne stany, a to iloczyn dwóch dużych liczb pierwszych i dających w dzieleniu przez 4 resztę 3 (dzięki czemu każda reszta kwadratowa modulo ma jeden pierwiastek kwadratowy, który także jest resztą kwadratową), i mających możliwie mały a jest funkcją Eulera (co zapewnia długi cykl). Wynikiem generatora jest kilka ostatnich bitów (pl)
- Blum Blum Shub (BBS) é um gerador de números pseudoaleatórios proposto por Lenore Blum, Manuel Blum e Michael Shub em 1986. O algoritmo BBS é: xn+1 = (xn)² mod M onde M=pq é o produto de dois números primos muito grandes p e q. Em cada passo do algoritmo, obtém-se um resultado para xn; o resultado é geralmente o bit de paridade de xn ou um ou mais dos bits menos significativos de xn. Uma característica interessante do gerador BBS é a possibilidade de calcular todo o valor xi de forma directa: (pt)
- Алгоритм Блюм — Блюма — Шуба (англ. Algorithm Blum — Blum — Shub, BBS) — генератор псевдослучайных чисел, предложенный в 1986 году Ленор Блюм, Мануэлем Блюмом и . BBS выглядит так: где является произведением двух больших простых и . На каждом шаге алгоритма выходные данные получаются из путём взятия либо бита чётности, либо одного или больше наименее значимых бит . , где — функция Кармайкла: в данном случае — наименьшее общее кратное чисел и . (ru)
- Blum Blum Shub (B.B.S.) är en pseudoslumptalsgenerator (PSTG) och är även kryptologiskt säker. B.B.S. har formen: . där utsignalen ofta presenteras som pariteten för xi , på formen z1, z2, … zi. Alla de log (log (M)) första bitarna är dock säkra att använda. Startvärdet x0 räknas fram genom formeln x0 = s2 (mod M), där s ska vara ett tal mellan 1 och M-1, tillhöra de naturliga talen och p och q ska inte vara en faktor i s. M är produkten mellan två unika tillräckligt stora p och q (M = pq), där p och q uppfyller: . . (sv)
- Алгоритм Блум - Блум - Шуба (англ. Algorithm Blum — Blum — Shub, BBS) - генератор псевдовипадкових чисел, запропонований в 1986 році , Мануелем Блумом і . BBS має такий вигляд: де є добуток двох великих простих чисел і . На кожному кроці алгоритму вихідні дані обчислюють з шляхом взяття або біта парності, або одного чи більше найменш значущих бітів . Два простих числа, і , повинні бути конгруентні з 3 по (це гарантує, що кожен квадратний залишок має один квадратний корінь, який також є квадратним залишком) і найбільший спільний дільник НСД має бути маленьким (це збільшує довжину циклу). , (uk)
|
