PDA

View Full Version : Blum-Blum-Shub questions


akimp3
April 28th, 2002, 15:30
Hi
i have read the blum blum shub algo in applied cryptography(Bruce Schiner).
As i have understand the program should be like this:
//p=7 q=19 n=133
#include<iostream.h>
main(){
int n=133;
int s=11;
int x[14];
int b[14];
x[0]=((s*s)%n); //x0=s^2 mod n
for (int i=0;i<14;i++)
{
x[I]=((x[i-1]*x[i-1])% n);
b[I]=x[I]&1;
cout<< b[I];
}
}
This program give me a 14 digit random that i can use for the
Password.My question is if I want to produce 10000 random passwords I have to give p and q 10000 different number that
produce n witch is a blum integer.The problem is that this
number should be produced randomly i mean i have to produce
a big quantity of prime number p and q each congruent to 3 modulo 4 and different from the latest produced number.
As my program should produce n batch of card and each batch
contain 10000 different password I don't know how to produce
p and q.
Please give me some hints.
Thank in advance

akimp3

mike
April 29th, 2002, 01:37
No, you only need one n ever.

n=p*q

p and q should be really big (like 512 bits)

You will need a bignum library to implement this code in such a way that it can't be broken. I suggest using Wei Dai's crypto++ library:

http://www.eskimo.com/~weidai

BBS will generate one bit per modular squaring. You need 14 log_2 10 bits = 47 bits for a 14-digit decimal number.

So for every 47 output bits, convert the bits from a 47-digit binary number into a 14-digit decimal number. Anyone who can predict your numbers can make a lot more money breaking into banks & other such stuff.

An even better way of getting your numbers is a true rng, not a pseudo-rng, based on thermal noise or something similar.

akimp3
April 29th, 2002, 15:53
Hi
thank you very much for your help.
I have understand completly my mistakes.
thanks
bye

akimp3
May 2nd, 2002, 15:45
Hi
thank Mike for your help.
I have downloaded the crypto++ but i had some problem with
it.I have used Miracl library(the one used by tE in RSA tools).
I think that my program is correct but I don't have any test data
that i can check it,do you have any sample data for the
Blum-Blum-Shub algo?

I have attached my source code and my exe file
to this post if anyone could tell me if everythings is correct.
@Mike:
about the 202 bit that you told me i have a little question
i want a 14 digit password each digit is beetween 0-9 so
i think that 46 bit is nedded could you please tell me if I
am wrong?

Thanks in advance

akimp3

mike
May 2nd, 2002, 19:30
I don't have test vectors, sorry. And 47 bits is right. I can't remember how I got 202. It's obviously way off.