]>
gitweb.pimeys.fr Git - NK2015_Client_Python_Alpha.git/blob - rsa_source/rsa/_version200.py
3 Module for calculating large primes, and RSA encryption, decryption,
4 signing and verification. Includes generating public and private keys.
6 WARNING: this implementation does not use random padding, compression of the
7 cleartext input to prevent repetitions, or other common security improvements.
12 __author__
= "Sybren Stuvel, Marloes de Boer, Ivo Tamboer, and Barry Mead"
13 __date__
= "2010-02-08"
22 # Display a warning that this insecure version is imported.
24 warnings
.warn('Insecure version of the RSA module is imported as %s' % __name__
)
28 """Returns the number of bits required to hold a specific long number"""
30 return int(math
.ceil(math
.log(number
,2)))
33 """Returns the greatest common divisor of p and q
37 # Iterateive Version is faster and uses much less stack space
39 if p
< q
: (p
,q
) = (q
,p
)
45 """Converts a list of bytes or a string to an integer
47 >>> (((128 * 256) + 64) * 256) + 15
50 >>> bytes2int(l) #same as bytes2int('\x80@\x0f')
54 if not (type(bytes
) is types
.ListType
or type(bytes
) is types
.StringType
):
55 raise TypeError("You must pass a string or a list")
57 # Convert byte stream to integer
61 if type(byte
) is types
.StringType
: byte
= ord(byte
)
66 def int2bytes(number
):
67 """Converts a number to a string of bytes
69 >>>int2bytes(123456789)
71 >>> bytes2int(int2bytes(123456789))
75 if not (type(number
) is types
.LongType
or type(number
) is types
.IntType
):
76 raise TypeError("You must pass a long or an int")
81 string
= "%s%s" % (chr(number
& 0xFF), string
)
87 """Converts a number in the range of 0 to 63 into base 64 digit
88 character in the range of '0'-'9', 'A'-'Z', 'a'-'z','-','_'.
94 if not (type(number
) is types
.LongType
or type(number
) is types
.IntType
):
95 raise TypeError("You must pass a long or an int")
97 if 0 <= number
<= 9: #00-09 translates to '0' - '9'
98 return chr(number
+ 48)
100 if 10 <= number
<= 35:
101 return chr(number
+ 55) #10-35 translates to 'A' - 'Z'
103 if 36 <= number
<= 61:
104 return chr(number
+ 61) #36-61 translates to 'a' - 'z'
106 if number
== 62: # 62 translates to '-' (minus)
109 if number
== 63: # 63 translates to '_' (underscore)
112 raise ValueError(u
'Invalid Base64 value: %i' % number
)
116 """Converts an ordinal character value in the range of
117 0-9,A-Z,a-z,-,_ to a number in the range of 0-63.
123 if not (type(number
) is types
.LongType
or type(number
) is types
.IntType
):
124 raise TypeError("You must pass a long or an int")
126 if 48 <= number
<= 57: #ord('0') - ord('9') translates to 0-9
129 if 65 <= number
<= 90: #ord('A') - ord('Z') translates to 10-35
132 if 97 <= number
<= 122: #ord('a') - ord('z') translates to 36-61
135 if number
== 45: #ord('-') translates to 62
138 if number
== 95: #ord('_') translates to 63
141 raise ValueError(u
'Invalid Base64 value: %i' % number
)
144 def int2str64(number
):
145 """Converts a number to a string of base64 encoded characters in
146 the range of '0'-'9','A'-'Z,'a'-'z','-','_'.
148 >>> int2str64(123456789)
152 if not (type(number
) is types
.LongType
or type(number
) is types
.IntType
):
153 raise TypeError("You must pass a long or an int")
158 string
= "%s%s" % (to64(number
& 0x3F), string
)
164 def str642int(string
):
165 """Converts a base64 encoded string into an integer.
166 The chars of this string in in the range '0'-'9','A'-'Z','a'-'z','-','_'
168 >>> str642int('7MyqL')
172 if not (type(string
) is types
.ListType
or type(string
) is types
.StringType
):
173 raise TypeError("You must pass a string or a list")
178 if type(byte
) is types
.StringType
: byte
= ord(byte
)
179 integer
+= from64(byte
)
183 def read_random_int(nbits
):
184 """Reads a random integer of approximately nbits bits rounded up
187 nbytes
= int(math
.ceil(nbits
/8.))
188 randomdata
= os
.urandom(nbytes
)
189 return bytes2int(randomdata
)
191 def randint(minvalue
, maxvalue
):
192 """Returns a random integer x with minvalue <= x <= maxvalue"""
194 # Safety - get a lot of random data even if the range is fairly
198 # The range of the random numbers we need to generate
199 range = (maxvalue
- minvalue
) + 1
201 # Which is this number of bytes
202 rangebytes
= ((bit_size(range) + 7) / 8)
204 # Convert to bits, but make sure it's always at least min_nbits*2
205 rangebits
= max(rangebytes
* 8, min_nbits
* 2)
207 # Take a random number of bits between min_nbits and rangebits
208 nbits
= random
.randint(min_nbits
, rangebits
)
210 return (read_random_int(nbits
) % range) + minvalue
213 """Calculates the value of the Jacobi symbol (a/b)
214 where both a and b are positive integers, and b is odd
221 if ((a
-1)*(b
-1) >> 2) & 1:
225 if (((b
* b
) - 1) >> 3) & 1:
231 def jacobi_witness(x
, n
):
232 """Returns False if n is an Euler pseudo-prime with base x, and
237 f
= pow(x
, (n
-1)/2, n
)
239 if j
== f
: return False
242 def randomized_primality_testing(n
, k
):
243 """Calculates whether n is composite (which is always correct) or
244 prime (which is incorrect with error probability 2**-k)
246 Returns False if the number is composite, and True if it's
250 # 50% of Jacobi-witnesses can report compositness of non-prime numbers
254 if jacobi_witness(x
, n
): return False
258 def is_prime(number
):
259 """Returns True if the number is prime, and False otherwise.
267 if randomized_primality_testing(number
, 6):
268 # Prime, according to Jacobi
276 """Returns a prime number of max. 'math.ceil(nbits/8)*8' bits. In
277 other words: nbits is rounded up to whole bytes.
289 integer
= read_random_int(nbits
)
295 if is_prime(integer
): break
301 def are_relatively_prime(a
, b
):
302 """Returns True if a and b are relatively prime, and False if they
305 >>> are_relatively_prime(2, 3)
307 >>> are_relatively_prime(2, 4)
315 """Returns a tuple of two different primes of nbits bits"""
316 pbits
= nbits
+ (nbits
/16) #Make sure that p and q aren't too close
317 qbits
= nbits
- (nbits
/16) #or the factoring programs can factor n
321 #Make sure p and q are different.
325 def extended_gcd(a
, b
):
326 """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
328 # r = gcd(a,b) i = multiplicitive inverse of a mod b
329 # or j = multiplicitive inverse of b mod a
330 # Neg return values for i or j are made positive mod b or a respectively
331 # Iterateive Version is faster and uses much less stack space
336 oa
= a
#Remember original a/b to remove
337 ob
= b
#negative values from return results
341 (x
, lx
) = ((lx
- (q
* x
)),x
)
342 (y
, ly
) = ((ly
- (q
* y
)),y
)
343 if (lx
< 0): lx
+= ob
#If neg wrap modulo orignal b
344 if (ly
< 0): ly
+= oa
#If neg wrap modulo orignal a
345 return (a
, lx
, ly
) #Return only positive values
347 # Main function: calculate encryption and decryption keys
348 def calculate_keys(p
, q
, nbits
):
349 """Calculates an encryption and a decryption key for p and q, and
350 returns them as a tuple (e, d)"""
353 phi_n
= (p
-1) * (q
-1)
356 # Make sure e has enough bits so we ensure "wrapping" through
358 e
= max(65537,getprime(nbits
/4))
359 if are_relatively_prime(e
, n
) and are_relatively_prime(e
, phi_n
): break
361 (d
, i
, j
) = extended_gcd(e
, phi_n
)
364 raise Exception("e (%d) and phi_n (%d) are not relatively prime" % (e
, phi_n
))
366 raise Exception("New extended_gcd shouldn't return negative values")
367 if not (e
* i
) % phi_n
== 1:
368 raise Exception("e (%d) and i (%d) are not mult. inv. modulo phi_n (%d)" % (e
, i
, phi_n
))
374 """Generate RSA keys of nbits bits. Returns (p, q, e, d).
376 Note: this can take a long time, depending on the key size.
379 (p
, q
) = find_p_q(nbits
)
380 (e
, d
) = calculate_keys(p
, q
, nbits
)
385 """Generates public and private keys, and returns them as (pub,
388 The public key consists of a dict {e: ..., , n: ....). The private
389 key consists of a dict {d: ...., p: ...., q: ....).
391 nbits
= max(9,nbits
) # Don't let nbits go below 9 bits
392 (p
, q
, e
, d
) = gen_keys(nbits
)
394 return ( {'e': e
, 'n': p
*q
}, {'d': d
, 'p': p
, 'q': q
} )
396 def encrypt_int(message
, ekey
, n
):
397 """Encrypts a message using encryption key 'ekey', working modulo n"""
399 if type(message
) is types
.IntType
:
400 message
= long(message
)
402 if not type(message
) is types
.LongType
:
403 raise TypeError("You must pass a long or int")
405 if message
< 0 or message
> n
:
406 raise OverflowError("The message is too long")
408 #Note: Bit exponents start at zero (bit counts start at 1) this is correct
409 safebit
= bit_size(n
) - 2 #compute safe bit (MSB - 1)
410 message
+= (1 << safebit
) #add safebit to ensure folding
412 return pow(message
, ekey
, n
)
414 def decrypt_int(cyphertext
, dkey
, n
):
415 """Decrypts a cypher text using the decryption key 'dkey', working
418 message
= pow(cyphertext
, dkey
, n
)
420 safebit
= bit_size(n
) - 2 #compute safe bit (MSB - 1)
421 message
-= (1 << safebit
) #remove safebit before decode
425 def encode64chops(chops
):
426 """base64encodes chops and combines them into a ',' delimited string"""
428 chips
= [] #chips are character chops
431 chips
.append(int2str64(value
))
433 #delimit chops with comma
434 encoded
= ','.join(chips
)
438 def decode64chops(string
):
439 """base64decodes and makes a ',' delimited string into chops"""
441 chips
= string
.split(',') #split chops at commas
445 for string
in chips
: #make char chops (chips) into chops
446 chops
.append(str642int(string
))
450 def chopstring(message
, key
, n
, funcref
):
451 """Chops the 'message' into integers that fit into n,
452 leaving room for a safebit to be added to ensure that all
453 messages fold during exponentiation. The MSB of the number n
454 is not independant modulo n (setting it could cause overflow), so
455 use the next lower bit for the safebit. Therefore reserve 2-bits
456 in the number n for non-data bits. Calls specified encryption
457 function for each chop.
459 Used by 'encrypt' and 'sign'.
462 msglen
= len(message
)
464 #Set aside 2-bits so setting of safebit won't overflow modulo n.
465 nbits
= bit_size(n
) - 2 # leave room for safebit
467 blocks
= msglen
/ nbytes
469 if msglen
% nbytes
> 0:
474 for bindex
in range(blocks
):
475 offset
= bindex
* nbytes
476 block
= message
[offset
:offset
+nbytes
]
477 value
= bytes2int(block
)
478 cypher
.append(funcref(value
, key
, n
))
480 return encode64chops(cypher
) #Encode encrypted ints to base64 strings
482 def gluechops(string
, key
, n
, funcref
):
483 """Glues chops back together into a string. calls
484 funcref(integer, key, n) for each chop.
486 Used by 'decrypt' and 'verify'.
490 chops
= decode64chops(string
) #Decode base64 strings into integer chops
493 mpart
= funcref(cpart
, key
, n
) #Decrypt each chop
494 message
+= int2bytes(mpart
) #Combine decrypted strings into a msg
498 def encrypt(message
, key
):
499 """Encrypts a string 'message' with the public key 'key'"""
501 raise Exception("You must use the public key with encrypt")
503 return chopstring(message
, key
['e'], key
['n'], encrypt_int
)
505 def sign(message
, key
):
506 """Signs a string 'message' with the private key 'key'"""
508 raise Exception("You must use the private key with sign")
510 return chopstring(message
, key
['d'], key
['p']*key
['q'], encrypt_int
)
512 def decrypt(cypher
, key
):
513 """Decrypts a string 'cypher' with the private key 'key'"""
515 raise Exception("You must use the private key with decrypt")
517 return gluechops(cypher
, key
['d'], key
['p']*key
['q'], decrypt_int
)
519 def verify(cypher
, key
):
520 """Verifies a string 'cypher' with the public key 'key'"""
522 raise Exception("You must use the public key with verify")
524 return gluechops(cypher
, key
['e'], key
['n'], decrypt_int
)
526 # Do doctest if we're not imported
527 if __name__
== "__main__":
531 __all__
= ["newkeys", "encrypt", "decrypt", "sign", "verify"]