ospaceteam /
outerspace
| @@ 402-422 (lines=21) @@ | ||
| 399 | return rsa.pem.save_pem(der, 'RSA PRIVATE KEY') |
|
| 400 | ||
| 401 | ||
| 402 | def extended_gcd(a, b): |
|
| 403 | """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb |
|
| 404 | """ |
|
| 405 | # r = gcd(a,b) i = multiplicitive inverse of a mod b |
|
| 406 | # or j = multiplicitive inverse of b mod a |
|
| 407 | # Neg return values for i or j are made positive mod b or a respectively |
|
| 408 | # Iterateive Version is faster and uses much less stack space |
|
| 409 | x = 0 |
|
| 410 | y = 1 |
|
| 411 | lx = 1 |
|
| 412 | ly = 0 |
|
| 413 | oa = a #Remember original a/b to remove |
|
| 414 | ob = b #negative values from return results |
|
| 415 | while b != 0: |
|
| 416 | q = a // b |
|
| 417 | (a, b) = (b, a % b) |
|
| 418 | (x, lx) = ((lx - (q * x)),x) |
|
| 419 | (y, ly) = ((ly - (q * y)),y) |
|
| 420 | if (lx < 0): lx += ob #If neg wrap modulo orignal b |
|
| 421 | if (ly < 0): ly += oa #If neg wrap modulo orignal a |
|
| 422 | return (a, lx, ly) #Return only positive values |
|
| 423 | ||
| 424 | def find_p_q(nbits, accurate=True): |
|
| 425 | ''''Returns a tuple of two different primes of nbits bits each. |
|
| @@ 325-345 (lines=21) @@ | ||
| 322 | if not q == p: break |
|
| 323 | return (p, q) |
|
| 324 | ||
| 325 | def extended_gcd(a, b): |
|
| 326 | """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb |
|
| 327 | """ |
|
| 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 |
|
| 332 | x = 0 |
|
| 333 | y = 1 |
|
| 334 | lx = 1 |
|
| 335 | ly = 0 |
|
| 336 | oa = a #Remember original a/b to remove |
|
| 337 | ob = b #negative values from return results |
|
| 338 | while b != 0: |
|
| 339 | q = long(a/b) |
|
| 340 | (a, b) = (b, a % b) |
|
| 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 |
|
| 346 | ||
| 347 | # Main function: calculate encryption and decryption keys |
|
| 348 | def calculate_keys(p, q, nbits): |
|
