Re: Cryptographically random numbers
Tim Hochberg <[EMAIL PROTECTED]> 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? -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
Paul Rubin wrote: > "Tuvas" <[EMAIL PROTECTED]> 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
"Tuvas" <[EMAIL PROTECTED]> 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
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... -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
"Tuvas" <[EMAIL PROTECTED]> writes: > from os import urandom > def cstring(bytes): > ret='' > while(len(ret) 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
Tuvas wrote: > from os import urandom > def cstring(bytes): > ret='' > while(len(ret) 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
Gervasio Bernal <[EMAIL PROTECTED]> 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
from os import urandom def cstring(bytes): ret='' while(len(ret)'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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
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:-) -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
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
--
http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
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:-) -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
"Tuvas" <[EMAIL PROTECTED]> 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) -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
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! -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
"Tuvas" <[EMAIL PROTECTED]> 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
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!
--
http://mail.python.org/mailman/listinfo/python-list
Re: Cryptographically random numbers
> 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 [EMAIL PROTECTED] -- http://mail.python.org/mailman/listinfo/python-list
Cryptographically random numbers
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! -- http://mail.python.org/mailman/listinfo/python-list
