fork download
copy 
  1. from Crypto.Util.number import *
  2.  
  3. def xgcd(a, b):
  4.     """Extended Euclidean Algorithm (Iterative)
  5.  
  6.     Args:
  7.         a: int
  8.         b: int
  9.  
  10.     NOTES
  11.     =====
  12.     We can represent gcd(a,b) = a.x + b.y
  13.     This function returns gcd(a, b), x, y
  14.  
  15.     REFERENCES
  16.     ==========
  17.     https://a...content-available-to-author-only...c.edu/331/notes/xgcd.pdf
  18.  
  19.     EXAMPLES
  20.     ========
  21.     >>> xgcd(15, 35)
  22.     (5, -2, 1)
  23.     >>> xgcd(30, 20)
  24.     (10, 1, -1)
  25.     """
  26.     assert a > 0 and b > 0
  27.  
  28.     xprev, x = 0, 1
  29.     yprev, y = 1, 0
  30.  
  31.     while a:
  32.         q = b // a
  33.         x, xprev = xprev - q * x, x
  34.         y, yprev = yprev - q * y, y
  35.         a, b = b % a, a
  36.  
  37.     return b, xprev, yprev
  38.  
  39. #openssl rsa -noout -text -inform PEM -in publickey.pem -pubin
  40. n = 6582416093028010331296659373009031197381159505574809084789080445968620671489531251341839807257414016347908553593373690756636759290807031891701228091164709
  41. # sq,b = gmpy2.iroot(n,2)
  42. # while n%sq != 0:
  43. #     sq += 1
  44. # p = sq
  45. # q = n / sq
  46.  
  47. # with open("ciphertext.txt") as f:
  48. #     ct = f.read()
  49. # ct = ct.decode('hex')
  50. # ct = bytes_to_long(ct)
  51. ct = 6406127376909895751144371473602121008927740899743590913049046328952056446854240587499914154405355759628588334083763124425035272951938386104796254276926677
  52.  
  53. q = int(110973448182064790315250114993940850027832200825996529312042086382625413926861)
  54. p = int(59315234417414827144869122702302197873013464220599601795902064496612053373369)
  55.  
  56. mp = pow(ct, int((p+1)/4), p)
  57. mq = pow(ct, int((q+1)/4), q)
  58.  
  59.  
  60. # from rsasim.gcd_utils import xgcd
  61. g, yp, yq = xgcd(p, q)
  62.  
  63. r = (yp*p*mq + yq*q*mp) % n
  64. mr = n - r
  65. s = (yp*p*mq - yq*q*mp) % n
  66. ms = n - s
  67.  
  68. for num in [r,mr,s,ms]:
  69.     print(long_to_bytes(num))
  70.  
Success #stdin #stdout 0.02s 8388KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

}�-��g+5����?��|�z��v*�d�w��_���8ϕ��4��e��8��T�r��K��+�H$
y[d ����n@ߢ��j��,;�9�w</O�''v�O%?�}�S��y���M;^�������\$NX��
R��á�Kr8�F�Ul9�@�di<��Ǿq�P>��D���Q�.-��E��wq_$$�	�̵Jb7
https://ideone.com/EonEzZ
language:
Python (cpython 2.7.16)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!