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
em***@fenx.com

[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]

Tuvas wrote:

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.
--
--Bryan

[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]

"Tuvas" <tu*****@gmail.com> writes:

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]

Paul Rubin wrote:

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)
--
--Bryan

[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]

"Tuvas" <tu*****@gmail.com> writes:

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]

Tuvas wrote:

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.
--
--Bryan

[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))

--
--Bryan

[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]

Bryan Olson wrote:

Tuvas wrote:

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.

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]

Gervasio Bernal <ge************@speedy.com.ar> writes:

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]

Tuvas wrote:

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]

"Tuvas" <tu*****@gmail.com> writes:

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]

Paul Rubin wrote:

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>

[Tuvas]

I've actually done the tests on this one, it's actually faster to use
the += than a list, odd as it may sound. I ran into this one a while
back. The best way to do it is to build an array from scratch, fill the
array, and then join it, but I didn't have time to do it that way...

[Steven D'Aprano]

On Tue, 07 Mar 2006 22:32:04 +0100, Fredrik Lundh wrote:

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.

As much as we all love optimizations, I'm unhappy about this one. It used
to be a real simple rule: to append lots of strings, use append/join. That
worked for any Python you used.

But now code that runs really fast in CPython 2.4 will run like a dog in
Jython or CPython 2.3. Python's implementation independence is weakened.

Worse, because nobody really knows what "often" means (or at least, those
who know haven't said) a conscientious Python developer who wants fast
performance now has to measure all his string appending code using both
idioms to be sure that *this particular case* is/isn't one of the "often".

Is there some heuristic for telling when CPython can do the in-place
appending, and when it can't? If we were talking about a tiny (1% say)
performance penalty for getting it wrong, then it wouldn't matter, but the
penalty for using += when the optimization doesn't apply is severe.
--
Steven.

[Paul Rubin]

"Tuvas" <tu*****@gmail.com> writes:

I've actually done the tests on this one, it's actually faster to use
the += than a list, odd as it may sound.

Frederik explained the reason; there's an optimization in Python 2.4
that I'd forgotten about, for that specific case. It's not in earlier
versions. It's a bit fragile in 2.4:

a = ''
for x in something:
a += g(x)

is fast, but if a is aliased, Python can't do the optimization, so

a = ''
b = a
for x in something:
a += g(x)

is slow. Figuring out which case to use relies on CPython's reference
counting storage allocator (the interpreter keeps track of how many
pointers there are to any given object) and so the optimization may
not be feasible at all in other implementations which use different
storage allocation strategies (e.g. Lisp-style garbage collection).

All in all I think it's best to use a completely different approach
(something like StringBuffer) but my effort to start a movement here
on clpy a couple months ago didn't get anywhere.

[Tim Hochberg]

Paul Rubin wrote:

"Tuvas" <tu*****@gmail.com> writes:

I've actually done the tests on this one, it's actually faster to use
the += than a list, odd as it may sound.

Frederik explained the reason; there's an optimization in Python 2.4
that I'd forgotten about, for that specific case. It's not in earlier
versions. It's a bit fragile in 2.4:

a = ''
for x in something:
a += g(x)

is fast, but if a is aliased, Python can't do the optimization, so

a = ''
b = a
for x in something:
a += g(x)

is slow.

Is this really true? After the first time through the loop, 'a' won't be
aliased any more since strings are immutable. After that the loops
should be equivalent. I tried this out to see if I could see a timing
difference, in case I was missing something, with Python 2.4.1, the
following two snippets timed essentially the same for N up to 2**20 (I
didn't try any higher):

def concat1():
a = ''
for x in ' '*N:
a += x
return a

def concat2():
a = ''
b = a
for x in ' '*N:
a += x
return a

Regards,
-tim
Figuring out which case to use relies on CPython's reference
counting storage allocator (the interpreter keeps track of how many
pointers there are to any given object) and so the optimization may
not be feasible at all in other implementations which use different
storage allocation strategies (e.g. Lisp-style garbage collection).

All in all I think it's best to use a completely different approach
(something like StringBuffer) but my effort to start a movement here
on clpy a couple months ago didn't get anywhere.

[Paul Rubin]

Tim Hochberg <ti**********@ieee.org> writes:

is fast, but if a is aliased, Python can't do the optimization, so

Is this really true? After the first time through the loop, 'a' won't
be aliased any more since strings are immutable.

Hmm, ok, there was some previous discussion of this problem and I
guess I mis-remembered it. Thanks. I think there is still a fairly
natural case where the optimization doesn't work. Anyone know?