Is this a CSPRNG or only PRNG?

[Vermute]

 

On this page I propose a new kind of algorithm to generate random numbers.

 

http://www.number.com.pt/index.html

 

My question is: Is this safe or not?

 

Thanks.

 

 

[khaled]

My question is: Is this safe or not?

 

1. A PRNG is Safe If and only If, the PRNG ,given the same input, gives the same output

If for the same input it give different output, It is Not Safe ...

 

2. A PRNG is Secure, given a serious of K outputs from an initial State S,

If using K, one can't get S .. If one can use K to get S then it is Not Secure ...

 

there are other things, you can lookup in Wikipedia too ...

 

Good luck, I have worked a Random Number Generator myself too,

but, it's not pseudo-random .. it's a total randomness ...

I'm going to publish my design after 4 months approximately,

 

I took a look into your algorithm, I think this is the algorithm:

 

LOCAL m AS QUAD
LOCAL n AS LONG
LOCAL a, b, x AS EXT

x=TIMER MOD 1

b=x^2

FOR m=2 TO 8193 DO a=b+1/m

FOR n=1 TO 16384 DO a+=x

x=(a*x+a) MOD 1

NEXT
NEXT

 

Your algorithm have some issues:

 

1. Performance: This algorithm takes more than (8192+16384) = (24576) Steps, just to generate 1 bit !

so saying you want to generate a K-bit Integer, you need (24576)*K .. which is not good !

Because you are basing your algorithm on binary .. with alot of operations ...

 

you can optimize this loop: FOR n=1 TO 16384 DO a+=x

into a single assignment: a += x * 16384

 

and optimize this loop: FOR m=2 TO 8193 DO a=b+1/m

into a single assignment: a = SUM OF b+1 * 1/m FOR m = (1..8192)+1

and since: aZ + bZ + cZ = Z * (a + b + c)

which gives: a = (b+1) * HARMONIC_SUM(1/m,1..8192)+1

 

you can define harmonic sum, look at this: http://mathworld.wolfram.com/HarmonicSeriesofPrimes.html

 

-------------------------------------------------

 

2. Safety: This algorithm is not safe, because you are doing alot of addictive mathematical operations,

on a 32-bit and 64-bit Integers, Where you will have tens of Overflows .. so, if you want to manage this

you have to as following:

 

LOCAL m AS LONG

LOCAL a AS LONG

 

FOR a = 1 TO 100000 DO m += a MOD LONG_MAX

 

in here, we jump the the border of overflow, but this will make you work only

on positive integers only !.. since: A MOD A = 0

 

also, it's not safe because of using the TIMER, because the random output should be based

on the input, not the current TIME\CLOCK, but if you mean using a TIMER like a STOP-WATCH

then that's still based on the input, this includes using an input-based CLOCK ...

 

--------------------------------------------------

 

Good luck

Edited January 21, 2011 by khaled

[Cap'n Refsmmat]

In BASIC, is "TIMER" some sort of timestamp? If so, you're basing your algorithm entirely on the current time, which is something an adversary may be able to easily guess. Strong cryptographically secure systems (like OpenBSD's) use system entropy, such as disk seek times and random bits of memory.

[khaled]

In BASIC, is "TIMER" some sort of timestamp? If so, you're basing your algorithm entirely on the current time, which is something an adversary may be able to easily guess. Strong cryptographically secure systems (like OpenBSD's) use system entropy, such as disk seek times and random bits of memory.

 

TIMER in Algorithm is the local clock, in Machine level it's the hardware clock.

[Cap'n Refsmmat]

Ah. In cryptography, the current time is not considered a great source of entropy.

[khaled]

Ah. In cryptography, the current time is not considered a great source of entropy.

 

I have experience in Cryptography field,

 

Time is used in Cryptography for Authentication, Authorization, One-time key, One-time Ticket,

Time-Integrated message exchange ...

 

But, if you use Time\Clock in a PRNG, then it's not Safe anymore,

but it gives you a good robustness ...

[insane_alien]

most operating systems have a good entropy pool. i think even windows does. why not just pull the seed from there every now and then? its going to be more random than the time which is sequential.

 

if you know the next seed will ALWAYS be higher than the last then it makes it easier to spoof.

[Vermute]

1. A PRNG is Safe If and only If, the PRNG ,given the same input, gives the same output

If for the same input it give different output, It is Not Safe ...

 

2. A PRNG is Secure, given a serious of K outputs from an initial State S,

If using K, one can't get S .. If one can use K to get S then it is Not Secure ...

 

there are other things, you can lookup in Wikipedia too ...

 

Good luck, I have worked a Random Number Generator myself too,

but, it's not pseudo-random .. it's a total randomness ...

I'm going to publish my design after 4 months approximately,

 

Tell me when you finish it.

I took a look into your algorithm, I think this is the algorithm:

 

LOCAL m AS QUAD
LOCAL n AS LONG
LOCAL a, b, x AS EXT

x=TIMER MOD 1

b=x^2

FOR m=2 TO 8193 DO a=b+1/m

FOR n=1 TO 16384 DO a+=x

x=(a*x+a) MOD 1

NEXT
NEXT

 

Your algorithm have some issues:

 

1. Performance: This algorithm takes more than (8192+16384) = (24576) Steps, just to generate 1 bit !

so saying you want to generate a K-bit Integer, you need (24576)*K .. which is not good !

Because you are basing your algorithm on binary .. with alot of operations ...

 

Here I don't agree with you.

Read performance on the page.

 

 

you can optimize this loop: FOR n=1 TO 16384 DO a+=x

into a single assignment: a += x * 16384

 

Here I don't agree with you too.

If I do a+=x*16384, I have big values for a, and that is not good for randomness.

and optimize this loop: FOR m=2 TO 8193 DO a=b+1/m

into a single assignment: a = SUM OF b+1 * 1/m FOR m = (1..8192)+1

and since: aZ + bZ + cZ = Z * (a + b + c)

which gives: a = (b+1) * HARMONIC_SUM(1/m,1..8192)+1

 

you can define harmonic sum, look at this: http://mathworld.wol...esofPrimes.html

 

-------------------------------------------------

 

2. Safety: This algorithm is not safe, because you are doing alot of addictive mathematical operations,

on a 32-bit and 64-bit Integers, Where you will have tens of Overflows .. so, if you want to manage this

you have to as following:

 

LOCAL m AS LONG

LOCAL a AS LONG

 

FOR a = 1 TO 100000 DO m += a MOD LONG_MAX

 

in here, we jump the the border of overflow, but this will make you work only

on positive integers only !.. since: A MOD A = 0

 

also, it's not safe because of using the TIMER, because the random output should be based

on the input, not the current TIME\CLOCK, but if you mean using a TIMER like a STOP-WATCH

then that's still based on the input, this includes using an input-based CLOCK ...

 

Go to http://www.number.com.pt/alvo.html and teste it well.

You can read the BASIC source code here: http://www.number.com.pt/source.html

 

--------------------------------------------------

 

Good luck

 

In BASIC, is "TIMER" some sort of timestamp? If so, you're basing your algorithm entirely on the current time, which is something an adversary may be able to easily guess. Strong cryptographically secure systems (like OpenBSD's) use system entropy, such as disk seek times and random bits of memory.

 

I used the TIMER function as an example.

Of corse, you can start the inicial state of x with a different value at your choice.

See http://www.number.com.pt/alvo.html where the inicial state of x, is your choice.

[khaled]

you can optimize this loop: FOR n=1 TO 16384 DO a+=x

into a single assignment: a += x * 16384

 

Here I don't agree with you too.

If I do a+=x*16384, I have big values for a, and that is not good for randomness.

 

You don't understand, the loop and the statement are the same operation,

in the loop you add x to a 16384, which is equal to adding x to a 16384 times,

which is adding x * 16384 to a ...

 

It's basic mathematics,

 

I have read your javascript source code on the website too ...

 

one more thing, my design is actually an Architecture for a Numerical Noise Generator, based on Noise Simulation ...

The source code is abstract and needs to implement many PRNGs for it to start working ...