Cryptographically random numbers

[Tuvas]

Okay, I'm working on devoloping a simple, cryptographically secure
number, from a range of numbers (As one might do for finding large
numbers, to test if they are prime). My function looks like this:

def cran_rand(min,max):
if(min>max):
x=max
max=min
min=x
range=round(log(max-min)/log(256))
if range==0:
range=1
num=max+1
while(num>max):
num=min+s2num(urandom(range))
return num

Any comments on this? I think it should hold up to a test, it seems to
work alright. Thanks!

 

[Emile van Sebille]

def cran_rand(min,max):

You're shadowing built-ins here. Not a problem, but something I'd generally
avoid.

if(min>max):
x=max
max=min
min=x

If the args were a,b you could say:

maxarg,minarg = min(a,b),max(a,b)

range=round(log(max-min)/log(256))

more builtin shadowing...

if range==0:
range=1

or as alt_name_for_range=... or 1

num=max+1
while(num>max):
num=min+s2num(urandom(range))

I'll assume os.urandom is urandom. What's s2num?

return num

Any comments on this? I think it should hold up to a test, it seems to
work alright. Thanks!

If this does what you want, that's good. But someday when you look again
and see

while(num>max): num=min+s2num(urandom(range))

you'll wonder...

Thankfully-python-uses-int-and-not-num-ly y'rs,

Emile van Sebille
(e-mail address removed)

 

[Tuvas]

Good idea about the max and min values. Yes, urandom is os.urandom.
s2num('blah') will convert the phrase blah to ascii, and treat them as
if they were a big function.

Anyone else whose still interested, I found another small bug, but it
was in the modular (Again). It won't do much, but...

I did test out the RSA from end to end, found another small bug (I
imputed the text luke, and it decrypted to ekul), but it works good
now. Hopefully there's nothing left gaping, thanks for the help!

 

[Bryan Olson]

Okay, I'm working on devoloping a simple, cryptographically secure
number, from a range of numbers (As one might do for finding large
numbers, to test if they are prime). My function looks like this:

def cran_rand(min,max):
if(min>max):
x=max
max=min
min=x
range=round(log(max-min)/log(256))
if range==0:
range=1
num=max+1
while(num>max):
num=min+s2num(urandom(range))
return num

Any comments on this? I think it should hold up to a test, it seems to
work alright.

Have to disagree. Try:

for _ in range(100):
print cran_rand(0, 500)

How many numbers greater than 255 do you get?


I have more comments, but that's the biggest issue.

 

[Tuvas]

Ahh, you are correct, that is a large bug... How about this one?

def s2num(text):
if(len(text)==1):
return ord(text)
else:
return ord(text[0])+256*s2num(text[1:])

def cran_rand(min,max):
range=int(log(abs(max-min))/log(2))+1
num=max+1
if range%8==0:
crange=range/8
else:
crange=range/8+1
while(num>max):
num=min+s2num(urandom(crange))%(2**range)
return num

 

[Paul Rubin]

def s2num(text):
if(len(text)==1):
return ord(text)
else:
return ord(text[0])+256*s2num(text[1:])

My favorite way to convert strings to numbers is with binascii:
from binascii import hexlify
def s2num(text):
return int(hexlify(text), 16)

def cran_rand(min,max):
range=int(log(abs(max-min))/log(2))+1

This is kind of ugly and I wonder if it's possible for roundoff error
in the log function to make the answer off by 1, if max-min is very
close to a power of 2.

 

[Bryan Olson]

My favorite way to convert strings to numbers is with binascii:
>
from binascii import hexlify
def s2num(text):
return int(hexlify(text), 16)

Neat. I use the empty string as a binary representation of zero,
which you can accommodate with:

def s2num(text):
return int(hexlify(text) or '0', 16)

 

[Tuvas]

Wait, I now see that there is a native base 2 log in python, so I will
just do that rather than my adhoc way. The reason for adding one is to
make sure there isn't any problems if the log is, for instance, 2.2. It
will always round up. It's better to have to try twice to make sure the
number can have the max range than never use the top half, as the first
version did... That changes the function to:

def cran_rand(min,max):
range=int(log(abs(max-min),2))+1
num=max+1
if range%8==0:
crange=range/8
else:
crange=range/8+1
while(num>max):
num=min+s2num(urandom(crange))%(2**range)
return num

As to the s2num(text), well, that looks really neat. Is there an easy
way to do the reverse of that? Thanks!

 

[Paul Rubin]

Wait, I now see that there is a native base 2 log in python, so I will
just do that rather than my adhoc way. The reason for adding one is to
make sure there isn't any problems if the log is, for instance, 2.2. It
will always round up. It's better to have to try twice to make sure the
number can have the max range than never use the top half, as the first
version did... That changes the function to:

OK, if the log is one too high, you just have to do a few additional
retries.

As to the s2num(text), well, that looks really neat. Is there an easy
way to do the reverse of that? Thanks!

from binascii import unhexlify
def num2s(n):
s = '%X' % n
if len(s) % 2 == 1:
s = '0' + s # make sure length of hex string is even
return unhexlify(s)

 

[Bryan Olson]

Ahh, you are correct, that is a large bug... How about this one?

Much better. Do note the comments from Emile van Sebille and Paul
Rubin. There are some minor style and efficiency points, but it
looks reasonable.

Incidentally, as of Python 2.4, the standard library offers
random.SystemRandom, which will generate integers in any desired
range using os.urandom as the entropy source.

 

[Tuvas]

Wow, that would have been nice to know... Oh well, I've already got the
function, might as well use it... I'm starting to learn alot more of
the standard libraries that exist for alot of the little functions. It
seems like every project I have I build a misc.py file that contains
several small, but useful functions, and quite often I discover there
is a system library function to do just that. Oh well. Still, I've gone
a long ways in my Python skills since I started 6 months ago

 

[Bryan Olson]

Tuvas wrote:
[...]

As to the s2num(text), well, that looks really neat. Is there an easy
way to do the reverse of that? Thanks!

Easy? Well, you be the judge:

def num2string(n):
""" Pass a non-negative int or long n.
Returns a string with bytes holding the big-endian base-256
representation of n. Zero is represented by the empty string.
"""
h = hex(n).lstrip('0x').rstrip('Ll')
if len(h) % 2:
h = '0' + h
return unhexlify(h)



I did a little testing:

for i in xrange(300):
assert s2num(num2string(i)) == i
for i in xrange(1, 20):
for _ in xrange(100):
r = os.urandom(i)
assert num2string(s2num(r)) == r.lstrip(chr(0))

 

[Tuvas]

Thanks for the function Paul, it works alot nicer than the one I had in
my program... Now, with all of this knowledge, I'm going to be brave
and try out everything with AES. It seems to be working alright, I'll
debug this more on my own than I did with my RSA code, which turned out
to be full of bugs... I know the program sends the blocks in the
reverse order that would be expected, but, well, I'll get there.
Cryptology is fun

 

[Gervasio Bernal]

Much better. Do note the comments from Emile van Sebille and Paul
Rubin. There are some minor style and efficiency points, but it
looks reasonable.

Incidentally, as of Python 2.4, the standard library offers
random.SystemRandom, which will generate integers in any desired
range using os.urandom as the entropy source.

How can I generate a random string containing digits, symbols and
letters? I will use this random string for the key of a cryptographic
algorithm.
Thanks

 

[Tuvas]

from os import urandom
def cstring(bytes):
ret=''
while(len(ret)<bytes):
c=os.urandom(1)
if c>'0' and c<'z':
ret=ret+c
return ret

That should do it, though I bet there might be a more efficient way. I
don't know if that's the set of characters you want to use, but... If
you want a better answer, you'd have to be more specific.

 

[Paul Rubin]

How can I generate a random string containing digits, symbols and
letters? I will use this random string for the key of a cryptographic
algorithm.

Generally if this is a string that some human user has to type in,
it's preferable to select some words randomly from a dictionary rather
than use an easily-garbled string of symbols. If the string will be
handled entirely by computers, just use a random string of bytes (like
os.urandom(20)) without worrying about whether they're printable
characters. If you really want a random-looking string of specific
characters, a simple way is:

usable_characters = string.letters + string.digits
...
# generate one character from the set (repeat as needed)
a,b = map(ord, os.urandom(2))
c = (a*256 + b) % len(usable_characters)

Notice that the characters will have slightly unequal probability
(unless the usable character set's size is a power of 2), but the
effect on the output entry is insignificant.

 

[Gervasio Bernal]

from os import urandom
def cstring(bytes):
ret=''
while(len(ret)<bytes):
c=os.urandom(1)
if c>'0' and c<'z':
ret=ret+c
return ret

That should do it, though I bet there might be a more efficient way. I
don't know if that's the set of characters you want to use, but... If
you want a better answer, you'd have to be more specific.

Thanks a lot, that is what I need.
If someone else have a more efficient way I will appreciate.

 

[Tuvas]

I will admit though, I have the same question as Paul, why do you want
a random string of numbers, letters, and symbols? But, you asked for
it, so, that'll do.

 

[Paul Rubin]

from os import urandom
def cstring(bytes):
ret=''
while(len(ret)<bytes):
c=os.urandom(1)
if c>'0' and c<'z':
ret=ret+c
return ret

That should do it, though I bet there might be a more efficient way.

One efficiency issue is that almost 90% of the os.urandom output gets
discarded. The other is more generic so I thought I'd mention it:

ret = ret + c

builds up a new string one character longer than the old value of ret,
then assigns ret to the new string. That is, the first time through
the loop (when ret is empty) it builds a 1-char string, the next time
it builds a 2-char string, etc. The total number of characters copied
around is approx 1+2+3+...+n where n is the final length, so it is
O(n**2). If n is very large (not the case for something like a password)
this gets expensive.

The usual Python idiom for building up a string in approx linear time
is:

def cstring(n):
ret = []
while (something):
ret.append(generate_another_character())
return ''.join(ret)

Python lists have a special efficiency hack so that ret.append doesn't
copy the whole list around, but rather, allocates space in bigger
chunks so that appending usually takes constant time. I don't think
this is part of the official specification but it's deeply ingrained
in Python culture and all kinds of Python code relies on it.

Another approach is to use Python's StringIO class (like Java
StringBuffer objects), but that's never been popular.

 

[Fredrik Lundh]

The usual Python idiom for building up a string in approx linear time
is:

def cstring(n):
ret = []
while (something):
ret.append(generate_another_character())
return ''.join(ret)

Python lists have a special efficiency hack so that ret.append doesn't
copy the whole list around, but rather, allocates space in bigger
chunks so that appending usually takes constant time.

in 2.4 and later, += on strings does the operation in place when
possible. this means that += is often faster than append/join.

</F>