32 bit random numbers

Anything QL Software or Programming Related.
User avatar
XorA
Site Admin
Posts: 1358
Joined: Thu Jun 02, 2011 11:31 am
Location: Shotts, North Lanarkshire, Scotland, UK

Re: 32 bit random numbers

Post by XorA »

bwinkel67 wrote:
XorA wrote:
repeatability and for cryptography and software engineering you want that
Hell no, crypto really likes true random for exactly the opposite of that reason.
The problem with true randomness is that when you encrypt something you can't decrypt it. What you want is the appearance of true randomness. There are lots of tests in the field of cryptography (mathematics) to address that. But in the end, if you can'f find the needle in the haystack then it's kind of worthless. So you may be conflating the idea o true randomness with the idea of pseudo randomness having all the properties of true randomness, which is what you want.

Remember that cryptography is an algorithmic solution and implemented in software. Hardware implementations are just more efficient implementations of that but AES is implemented in your version of SSH and by that nature they can't be implementing true randomness, just the appearance of it.
Basically you are wrong here, you are conflating entropy and randomness!

Your crypto keys almost certainly these days were generated from a true random generator on any modern OS on any modern CPU. Otherwise you get into the problem of guessable keys. (looking at you RiscOS and debian)


User avatar
bwinkel67
QL Wafer Drive
Posts: 1187
Joined: Thu Oct 03, 2019 2:09 am

Re: 32 bit random numbers

Post by bwinkel67 »

XorA wrote: Your crypto keys almost certainly these days were generated from a true random generator on any modern OS on any modern CPU. Otherwise you get into the problem of guessable keys. (looking at you RiscOS and debian)
So a "key" in cryptography is your starting point and can be generated by a truly random method, that being someone's brain. Usually this can be derived from a password via a hashing method. I suppose you can use an OS clock on a commuter. However, this is input to AES and DES and that key needs to be captured and kept somewhere safe. After that it's all deterministic. Check out the text I uploaded as it gives a complete algorithmic description of all the rounds of both DES and AES. I've implemented DES in C (just not on the QL) and it's all deterministic bit twiddling. AES uses more complex matrix multiplication but there is no continuous outside source of true randomness other than the starting one which is supplied by the user.

Note that you can encrypt information using DES and AES completely independent of a computer. I've had students encrypt text using DES with pen and paper as an exercise and though it's a pain, it's pretty neat to see it work.


User avatar
bwinkel67
QL Wafer Drive
Posts: 1187
Joined: Thu Oct 03, 2019 2:09 am

Re: 32 bit random numbers

Post by bwinkel67 »

XorA wrote: Your crypto keys almost certainly these days were generated from a true random generator on any modern OS on any modern CPU. Otherwise you get into the problem of guessable keys. (looking at you RiscOS and debian)
So trying to understand what you are trying to say here a bit more...I think I may know what you are trying to say...apologies if I still misunderstand.

So AES and DES are block ciphers. If you use them you feed to them a key and it uses that key to encrypt text. That key needs to be kept so that it can be used to decrypt.

However, in many implementations as they relate to the internet/web, when a tunnel between client/server is created and that tunnel is encrypted (with AES), coming up with the key to start that process can be generated automatically and here it is worthwhile to have it be arbitrary and truly random, i.e. the clock of how long a computer has been running, which from my days hacking the Mac OS I used as process ID, but can also be used to seed a pseudo random number generator (if you don't want to seed it yourself). So when using SSH to connect to a server, that is exactly what happens. SSH uses Diffie-Hellman (a public key exchange algorithm) to do a secret key exchange and that algorithm needs both sides to choose arbitrary, random keys (one each), and through shared information, it generates a shared key that only the server and client can figure out since each of their secrets are kept private. So then using that generated shared key (derived from two arbitrary, true random keys) AES can encrypt on one side and decrypt on the other side. AES is still deterministic but because the key is unknown, a hacker cannot determine what is being encrypted. So with that context, yes, true randomness is important but that's not really part of cryptography and more a part of its implementation/deployment on actual systems/technology on the internet/web. So likely this is where our disconnect in the discussion came from.

Let me know if that makes sense.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: 32 bit random numbers

Post by stevepoole »

Hi Bwinkel,

Yes, your explanations do make sense, and correspond to what is written in the detailed pdf file you posted.

The question is, to what extent is the 32bit random routine TRUE RANDOM ? I am no expert on the subject, but it must be far better than 'congruent' routines ?

I cannot imagine that this program could produce repeated results, even using a reset 128 ko QL.... although I don't have one to test with ! (Uses a DATE seed).

There are 32bit random number generators on the web, but not the code to do it with...

Anyway, beside potential use discussions, I would like to know if anyone has found any bugs.

Steve.
_____________


User avatar
bwinkel67
QL Wafer Drive
Posts: 1187
Joined: Thu Oct 03, 2019 2:09 am

Re: 32 bit random numbers

Post by bwinkel67 »

stevepoole wrote:Hi Bwinkel,

Yes, your explanations do make sense, and correspond to what is written in the detailed pdf file you posted.

The question is, to what extent is the 32bit random routine TRUE RANDOM ? I am no expert on the subject, but it must be far better than 'congruent' routines ?

I cannot imagine that this program could produce repeated results, even using a reset 128 ko QL.... although I don't have one to test with ! (Uses a DATE seed).

There are 32bit random number generators on the web, but not the code to do it with...

Anyway, beside potential use discussions, I would like to know if anyone has found any bugs.

Steve.
_____________
I'm not quite sure what you are asking. The Linear Congruent Random Number Generator Park-Miller (which is 31 bits in sequence size) is sufficiently random that for any set of normal operations (gaming, software engineering, etc) it will appear random. If you are trying to use it in cryptography then it is not sufficient and there are better ones out there. Blum-Micali and Blum-Blum-Shub are two cryptographically secure pseudo random number generators used. There should be a wikipedia page on both.

The idea of true randomness has some uses but as I said, in many cases you want repeatability, i.e. in software engineering you may want to create a random sequence to test the I/O of software but when you discover a bug and fix it, you want to recreate that exact same random sequence so you can be sure you fixed it. My comments on repeatability in cryptography is that you want the same key to give you the same encryption given the same input since to decrypt, generally, you do the reverse.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: 32 bit random numbers

Post by stevepoole »

Hi Folks,

The question asked was : Is the program TRUE random ? In order to answer, I wrote a program to test the QL's RND(0 to 1) code.

If the RND(1) code is truly random, the picture should be mostly full of mush. But straight coloured lines reveal any repeated digits...

But as the rand31(mn,mx) routine acts on individual bits in constructing the random number, this slight bias is diluted considerably.

So, I suppose that the rand31() code produces better random numbers than QL ROM, (except for rand31(0,1) ! )

I hope you find the rand31() program useful ?

Steve.
Capture d’écran (494)bis.jpg


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: 32 bit random numbers

Post by stevepoole »

Hi again,

The previous screen was a test on bias. This one simply shows rand31(0 to 1) on the left, and rnd(1) on the right.

Can you spot any difference ?

Steve.
_______________
Capture d’écran (495)bis.jpg


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: 32 bit random numbers

Post by stevepoole »

Hi,

Screens 1: rand31(0,32767) on left, rnd(32767) on right.

Screen 2: rand(0; (2^31)-1)

All seem Ok.

Steve.
_________________
Capture d’écran (496)bis.jpg
Capture d’écran (496)bis.jpg
Attachments
Capture d’écran (497)bis.jpg


User avatar
bwinkel67
QL Wafer Drive
Posts: 1187
Joined: Thu Oct 03, 2019 2:09 am

Re: 32 bit random numbers

Post by bwinkel67 »

Hi Steve,

Here is an interesting article (way back from 1986 I believe) that I came upon last year that I had my students look at. We looked at scatter plots of various historical random number generators and sort of discovered what this paper alludes to, which is that they are ok but not perfect tools to judge how good one is.
a177054.pdf
(1.06 MiB) Downloaded 59 times
Btw, Stephen Park, the Park in Park-Miller was one of my mentors (teachers) growing up. I was a mathematician in school and he worked in simulations (not security). Unfortunately he passed away around 2000 at an early age. My research area moved into AI over the past 25 years, doing speech recognition, but having a math background, once we had a need for security courses at my college I was tasked with teaching them. That's why I had the opportunity of teaching a cryptography course. Before that I was teaching a more general security course and stumbled upon Park-Miller as a random number generator that I used in some of my lab work (constructing a primitive stream cipher for students to work on) only to discover a few years into it that Park in Park-Miller was Stephen Park. It was kind of cool how it all came back around in my adult years using one of my teacher's work as a teacher. Stephen would always hound me and point out some of my flaws in class so he was not one of my favorite teachers then, but as time wore on I realized he had had such a profound impact on how I do things now.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: 32 bit random numbers

Post by stevepoole »

Hi Bwinkel,

Yes, the inconvenience of scatter plots is that they are limited by screen resolution, in the case of the QL, 512x256.

Admittedly, the QL can SCALE (2^31)-1,0,0, but with 32bit random numbers, dots are overprinted onto each other. The solution is to zoom, by selecting ranges of 256, say Rand32(0,255), or n=(2^31)-1 : rand32(n-255,n), with SCALE 255,0,0; or whatever range slice you choose. Such scatter plots show equivalence for all ranges tested !

I use a 'for loop=1 to 2*255*255', with x=rnd32(range) & y=rnd32(range) where overprinted points can be revealed by XORing them to produce speckle animation.

My first (coloured) screen consisted of bar-charts of '0' an '1' totalised biases. That is far more revealing than scatter plotting the same values...

But after very long series of loops, total variance diminishes to a factor of around 0.998, which tends to even out over time.

I have used arrays to record values, but these are limited to the range of 32768, and again require zooming so as to be significant via 'zoom sampling'.

I could always use PEEK and POKE with larger reserved memory areas, but do not see that that would improve statistical analysis.

Thank you for the interesting pdf file. QPC2 runs on my 64bit computer, but does not use the processor's full random potential... yet ?

Steve.
_____________________


Post Reply