rsa_source/rsa/_version133.py

   1 """RSA module
   2 pri = k[1]                                      //Private part of keys d,p,q
   3
   4 Module for calculating large primes, and RSA encryption, decryption,
   5 signing and verification. Includes generating public and private keys.
   6
   7 WARNING: this code implements the mathematics of RSA. It is not suitable for
   8 real-world secure cryptography purposes. It has not been reviewed by a security
   9 expert. It does not include padding of data. There are many ways in which the
  10 output of this module, when used without any modification, can be sucessfully
  11 attacked.
  12 """
  13
  14 __author__ = "Sybren Stuvel, Marloes de Boer and Ivo Tamboer"
  15 __date__ = "2010-02-05"
  16 __version__ = '1.3.3'
  17
  18 # NOTE: Python's modulo can return negative numbers. We compensate for
  19 # this behaviour using the abs() function
  20
  21 from cPickle import dumps, loads
  22 import base64
  23 import math
  24 import os
  25 import random
  26 import sys
  27 import types
  28 import zlib
  29
  30 # Display a warning that this insecure version is imported.
  31 import warnings
  32 warnings.warn('Insecure version of the RSA module is imported as %s, be careful'
  33         % __name__)
  34
  35 def gcd(p, q):
  36     """Returns the greatest common divisor of p and q
  37
  38
  39     >>> gcd(42, 6)
  40     6
  41     """
  42     if p<q: return gcd(q, p)
  43     if q == 0: return p
  44     return gcd(q, abs(p%q))
  45
  46 def bytes2int(bytes):
  47     """Converts a list of bytes or a string to an integer
  48
  49     >>> (128*256 + 64)*256 + + 15
  50     8405007
  51     >>> l = [128, 64, 15]
  52     >>> bytes2int(l)
  53     8405007
  54     """
  55
  56     if not (type(bytes) is types.ListType or type(bytes) is types.StringType):
  57         raise TypeError("You must pass a string or a list")
  58
  59     # Convert byte stream to integer
  60     integer = 0
  61     for byte in bytes:
  62         integer *= 256
  63         if type(byte) is types.StringType: byte = ord(byte)
  64         integer += byte
  65
  66     return integer
  67
  68 def int2bytes(number):
  69     """Converts a number to a string of bytes
  70
  71     >>> bytes2int(int2bytes(123456789))
  72     123456789
  73     """
  74
  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")
  77
  78     string = ""
  79
  80     while number > 0:
  81         string = "%s%s" % (chr(number & 0xFF), string)
  82         number /= 256
  83
  84     return string
  85
  86 def fast_exponentiation(a, p, n):
  87     """Calculates r = a^p mod n
  88     """
  89     result = a % n
  90     remainders = []
  91     while p != 1:
  92         remainders.append(p & 1)
  93         p = p >> 1
  94     while remainders:
  95         rem = remainders.pop()
  96         result = ((a ** rem) * result ** 2) % n
  97     return result
  98
  99 def read_random_int(nbits):
 100     """Reads a random integer of approximately nbits bits rounded up
 101     to whole bytes"""
 102
 103     nbytes = ceil(nbits/8.)
 104     randomdata = os.urandom(nbytes)
 105     return bytes2int(randomdata)
 106
 107 def ceil(x):
 108     """ceil(x) -> int(math.ceil(x))"""
 109
 110     return int(math.ceil(x))
 111
 112 def randint(minvalue, maxvalue):
 113     """Returns a random integer x with minvalue <= x <= maxvalue"""
 114
 115     # Safety - get a lot of random data even if the range is fairly
 116     # small
 117     min_nbits = 32
 118
 119     # The range of the random numbers we need to generate
 120     range = maxvalue - minvalue
 121
 122     # Which is this number of bytes
 123     rangebytes = ceil(math.log(range, 2) / 8.)
 124
 125     # Convert to bits, but make sure it's always at least min_nbits*2
 126     rangebits = max(rangebytes * 8, min_nbits * 2)
 127
 128     # Take a random number of bits between min_nbits and rangebits
 129     nbits = random.randint(min_nbits, rangebits)
 130
 131     return (read_random_int(nbits) % range) + minvalue
 132
 133 def fermat_little_theorem(p):
 134     """Returns 1 if p may be prime, and something else if p definitely
 135     is not prime"""
 136
 137     a = randint(1, p-1)
 138     return fast_exponentiation(a, p-1, p)
 139
 140 def jacobi(a, b):
 141     """Calculates the value of the Jacobi symbol (a/b)
 142     """
 143
 144     if a % b == 0:
 145         return 0
 146     result = 1
 147     while a > 1:
 148         if a & 1:
 149             if ((a-1)*(b-1) >> 2) & 1:
 150                 result = -result
 151             b, a = a, b % a
 152         else:
 153             if ((b ** 2 - 1) >> 3) & 1:
 154                 result = -result
 155             a = a >> 1
 156     return result
 157
 158 def jacobi_witness(x, n):
 159     """Returns False if n is an Euler pseudo-prime with base x, and
 160     True otherwise.
 161     """
 162
 163     j = jacobi(x, n) % n
 164     f = fast_exponentiation(x, (n-1)/2, n)
 165
 166     if j == f: return False
 167     return True
 168
 169 def randomized_primality_testing(n, k):
 170     """Calculates whether n is composite (which is always correct) or
 171     prime (which is incorrect with error probability 2**-k)
 172
 173     Returns False if the number if composite, and True if it's
 174     probably prime.
 175     """
 176
 177     q = 0.5     # Property of the jacobi_witness function
 178
 179     # t = int(math.ceil(k / math.log(1/q, 2)))
 180     t = ceil(k / math.log(1/q, 2))
 181     for i in range(t+1):
 182         x = randint(1, n-1)
 183         if jacobi_witness(x, n): return False
 184
 185     return True
 186
 187 def is_prime(number):
 188     """Returns True if the number is prime, and False otherwise.
 189
 190     >>> is_prime(42)
 191     0
 192     >>> is_prime(41)
 193     1
 194     """
 195
 196     """
 197     if not fermat_little_theorem(number) == 1:
 198         # Not prime, according to Fermat's little theorem
 199         return False
 200     """
 201
 202     if randomized_primality_testing(number, 5):
 203         # Prime, according to Jacobi
 204         return True
 205
 206     # Not prime
 207     return False
 208
 209
 210 def getprime(nbits):
 211     """Returns a prime number of max. 'math.ceil(nbits/8)*8' bits. In
 212     other words: nbits is rounded up to whole bytes.
 213
 214     >>> p = getprime(8)
 215     >>> is_prime(p-1)
 216     0
 217     >>> is_prime(p)
 218     1
 219     >>> is_prime(p+1)
 220     0
 221     """
 222
 223     nbytes = int(math.ceil(nbits/8.))
 224
 225     while True:
 226         integer = read_random_int(nbits)
 227
 228         # Make sure it's odd
 229         integer |= 1
 230
 231         # Test for primeness
 232         if is_prime(integer): break
 233
 234         # Retry if not prime
 235
 236     return integer
 237
 238 def are_relatively_prime(a, b):
 239     """Returns True if a and b are relatively prime, and False if they
 240     are not.
 241
 242     >>> are_relatively_prime(2, 3)
 243     1
 244     >>> are_relatively_prime(2, 4)
 245     0
 246     """
 247
 248     d = gcd(a, b)
 249     return (d == 1)
 250
 251 def find_p_q(nbits):
 252     """Returns a tuple of two different primes of nbits bits"""
 253
 254     p = getprime(nbits)
 255     while True:
 256         q = getprime(nbits)
 257         if not q == p: break
 258
 259     return (p, q)
 260
 261 def extended_euclid_gcd(a, b):
 262     """Returns a tuple (d, i, j) such that d = gcd(a, b) = ia + jb
 263     """
 264
 265     if b == 0:
 266         return (a, 1, 0)
 267
 268     q = abs(a % b)
 269     r = long(a / b)
 270     (d, k, l) = extended_euclid_gcd(b, q)
 271
 272     return (d, l, k - l*r)
 273
 274 # Main function: calculate encryption and decryption keys
 275 def calculate_keys(p, q, nbits):
 276     """Calculates an encryption and a decryption key for p and q, and
 277     returns them as a tuple (e, d)"""
 278
 279     n = p * q
 280     phi_n = (p-1) * (q-1)
 281
 282     while True:
 283         # Make sure e has enough bits so we ensure "wrapping" through
 284         # modulo n
 285         e = getprime(max(8, nbits/2))
 286         if are_relatively_prime(e, n) and are_relatively_prime(e, phi_n): break
 287
 288     (d, i, j) = extended_euclid_gcd(e, phi_n)
 289
 290     if not d == 1:
 291         raise Exception("e (%d) and phi_n (%d) are not relatively prime" % (e, phi_n))
 292
 293     if not (e * i) % phi_n == 1:
 294         raise Exception("e (%d) and i (%d) are not mult. inv. modulo phi_n (%d)" % (e, i, phi_n))
 295
 296     return (e, i)
 297
 298
 299 def gen_keys(nbits):
 300     """Generate RSA keys of nbits bits. Returns (p, q, e, d).
 301
 302     Note: this can take a long time, depending on the key size.
 303     """
 304
 305     while True:
 306         (p, q) = find_p_q(nbits)
 307         (e, d) = calculate_keys(p, q, nbits)
 308
 309         # For some reason, d is sometimes negative. We don't know how
 310         # to fix it (yet), so we keep trying until everything is shiny
 311         if d > 0: break
 312
 313     return (p, q, e, d)
 314
 315 def gen_pubpriv_keys(nbits):
 316     """Generates public and private keys, and returns them as (pub,
 317     priv).
 318
 319     The public key consists of a dict {e: ..., , n: ....). The private
 320     key consists of a dict {d: ...., p: ...., q: ....).
 321     """
 322
 323     (p, q, e, d) = gen_keys(nbits)
 324
 325     return ( {'e': e, 'n': p*q}, {'d': d, 'p': p, 'q': q} )
 326
 327 def encrypt_int(message, ekey, n):
 328     """Encrypts a message using encryption key 'ekey', working modulo
 329     n"""
 330
 331     if type(message) is types.IntType:
 332         return encrypt_int(long(message), ekey, n)
 333
 334     if not type(message) is types.LongType:
 335         raise TypeError("You must pass a long or an int")
 336
 337     if message > 0 and \
 338             math.floor(math.log(message, 2)) > math.floor(math.log(n, 2)):
 339         raise OverflowError("The message is too long")
 340
 341     return fast_exponentiation(message, ekey, n)
 342
 343 def decrypt_int(cyphertext, dkey, n):
 344     """Decrypts a cypher text using the decryption key 'dkey', working
 345     modulo n"""
 346
 347     return encrypt_int(cyphertext, dkey, n)
 348
 349 def sign_int(message, dkey, n):
 350     """Signs 'message' using key 'dkey', working modulo n"""
 351
 352     return decrypt_int(message, dkey, n)
 353
 354 def verify_int(signed, ekey, n):
 355     """verifies 'signed' using key 'ekey', working modulo n"""
 356
 357     return encrypt_int(signed, ekey, n)
 358
 359 def picklechops(chops):
 360     """Pickles and base64encodes it's argument chops"""
 361
 362     value = zlib.compress(dumps(chops))
 363     encoded = base64.encodestring(value)
 364     return encoded.strip()
 365
 366 def unpicklechops(string):
 367     """base64decodes and unpickes it's argument string into chops"""
 368
 369     return loads(zlib.decompress(base64.decodestring(string)))
 370
 371 def chopstring(message, key, n, funcref):
 372     """Splits 'message' into chops that are at most as long as n,
 373     converts these into integers, and calls funcref(integer, key, n)
 374     for each chop.
 375
 376     Used by 'encrypt' and 'sign'.
 377     """
 378
 379     msglen = len(message)
 380     mbits = msglen * 8
 381     nbits = int(math.floor(math.log(n, 2)))
 382     nbytes = nbits / 8
 383     blocks = msglen / nbytes
 384
 385     if msglen % nbytes > 0:
 386         blocks += 1
 387
 388     cypher = []
 389
 390     for bindex in range(blocks):
 391         offset = bindex * nbytes
 392         block = message[offset:offset+nbytes]
 393         value = bytes2int(block)
 394         cypher.append(funcref(value, key, n))
 395
 396     return picklechops(cypher)
 397
 398 def gluechops(chops, key, n, funcref):
 399     """Glues chops back together into a string.  calls
 400     funcref(integer, key, n) for each chop.
 401
 402     Used by 'decrypt' and 'verify'.
 403     """
 404     message = ""
 405
 406     chops = unpicklechops(chops)
 407
 408     for cpart in chops:
 409         mpart = funcref(cpart, key, n)
 410         message += int2bytes(mpart)
 411
 412     return message
 413
 414 def encrypt(message, key):
 415     """Encrypts a string 'message' with the public key 'key'"""
 416
 417     return chopstring(message, key['e'], key['n'], encrypt_int)
 418
 419 def sign(message, key):
 420     """Signs a string 'message' with the private key 'key'"""
 421
 422     return chopstring(message, key['d'], key['p']*key['q'], decrypt_int)
 423
 424 def decrypt(cypher, key):
 425     """Decrypts a cypher with the private key 'key'"""
 426
 427     return gluechops(cypher, key['d'], key['p']*key['q'], decrypt_int)
 428
 429 def verify(cypher, key):
 430     """Verifies a cypher with the public key 'key'"""
 431
 432     return gluechops(cypher, key['e'], key['n'], encrypt_int)
 433
 434 # Do doctest if we're not imported
 435 if __name__ == "__main__":
 436     import doctest
 437     doctest.testmod()
 438
 439 __all__ = ["gen_pubpriv_keys", "encrypt", "decrypt", "sign", "verify"]
 440