elvanderb

PHDays Quals 2014: mars (multiprime RSA + common factor)

Jan 27th, 2014
621
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # > REQUEST EXCHANGE
  2. # < CONFIRMED
  3. # > KEY 7abed4245dec0a5df17c672d799488c7b5ef5b9110c43e0c3eae586c21b7369095569fc3aa0cc2cde94a362cc6e7902b8bb1bd6d32f358d8e7091e7e8c48b9fa2aabe1579328cfa18e55927c5e9c7d50ccba5b5f4e173b606b65a95c6f6c27b9fa8b482c45ce9605700856869b2beb7f663bf6244902ab57bf681a31fdbe86d7107daa7cc53dcff6633cb7a591508da29e1016dc85211f83052efc8e987e4d5cf5bac407ee187795dbba722e8b3650c555d119c55676a5ff90af6a0eabbba477/010001
  4. # < KEY 55b0a8cbba652468362b92444a4336da542eb8641ac83fc85e4e44bc77965842aa18f783d150a03a084f04e6809ee60e5bfe8379397a665936d91b5f3433b48339d22b8b3de2544898376c87ddc385b8e6994eda6e385996a102a6cf5e241dbb0c78eae345c01a1bdad9d30d9bf84c02d976965654ec028d965833bd7072fbeb8c576b49cc9f666757300fca0877f88a0975b3b5c67555f1de17aa153d2b9b54c6a51bcb35ca840e7f5cabdb1bd4eab542cbae8a2dd5a59f8e84785089bdd383/010001
  5. # > MSG 2cb5e614c40eb325cdcec0410884b5e4b20cb63c39f93b720710b2b4a2d66b76588129d24172faf0ef84ca02b3f89b718eaf2a7ba7a13e444a7772ed79b3db6c621c02a0d32ec09c510fcd39b1c76d715507de8634d217dceb33cb4d0cb0309b58bf89e4e27e6ab0a24c32f97d820013cefcd35408e12d11644928a368526d1482503995c0d3921164fc0b301329ffb1aac13f66dcaa21a6f63e371308be12366de0e68db27751ec12f9e02976bc52b2a2888f07608d26a637a46f03a6f1a1ab
  6. # < MSG 3c94c8dffb44880a13acc3e40826d021e4da41aca832cb6d396e83f528eb6fdd4aed8f59ed837d072230b0d6e38e57d90dd409de1c2e867a5b6a3962a83aa330b12516c313b0ba4820887fc7761c673d223b51f4f97ed1a7a90a009a880f7317b3681a8ca64b53f2416d7daf43b8da2358d19d7e38d10c22bf7c55cf8fb587d33b9ee87492149ad959c0154b4708c5961705f08a45423d4f5cabcbb3b2ec43266589ac3dbaf72a88377b9fe2afa84be2feacdb622f508d5d2874fa3106334bbd
  7.  
  8. a = 0x7abed4245dec0a5df17c672d799488c7b5ef5b9110c43e0c3eae586c21b7369095569fc3aa0cc2cde94a362cc6e7902b8bb1bd6d32f358d8e7091e7e8c48b9fa2aabe1579328cfa18e55927c5e9c7d50ccba5b5f4e173b606b65a95c6f6c27b9fa8b482c45ce9605700856869b2beb7f663bf6244902ab57bf681a31fdbe86d7107daa7cc53dcff6633cb7a591508da29e1016dc85211f83052efc8e987e4d5cf5bac407ee187795dbba722e8b3650c555d119c55676a5ff90af6a0eabbba477
  9.  
  10. b = 0x55b0a8cbba652468362b92444a4336da542eb8641ac83fc85e4e44bc77965842aa18f783d150a03a084f04e6809ee60e5bfe8379397a665936d91b5f3433b48339d22b8b3de2544898376c87ddc385b8e6994eda6e385996a102a6cf5e241dbb0c78eae345c01a1bdad9d30d9bf84c02d976965654ec028d965833bd7072fbeb8c576b49cc9f666757300fca0877f88a0975b3b5c67555f1de17aa153d2b9b54c6a51bcb35ca840e7f5cabdb1bd4eab542cbae8a2dd5a59f8e84785089bdd383
  11.  
  12. c = 0x3c94c8dffb44880a13acc3e40826d021e4da41aca832cb6d396e83f528eb6fdd4aed8f59ed837d072230b0d6e38e57d90dd409de1c2e867a5b6a3962a83aa330b12516c313b0ba4820887fc7761c673d223b51f4f97ed1a7a90a009a880f7317b3681a8ca64b53f2416d7daf43b8da2358d19d7e38d10c22bf7c55cf8fb587d33b9ee87492149ad959c0154b4708c5961705f08a45423d4f5cabcbb3b2ec43266589ac3dbaf72a88377b9fe2afa84be2feacdb622f508d5d2874fa3106334bbd
  13.  
  14. e = 0x010001
  15.  
  16.  
  17. def xgcd(a,b):
  18.     """xgcd(a,b) returns a list of form [g,x,y], where g is gcd(a,b) and
  19.    x,y satisfy the equation g = ax + by."""
  20.     a1=1; b1=0; a2=0; b2=1; aneg=1; bneg=1
  21.     if(a < 0):
  22.         a = -a; aneg=-1
  23.     if(b < 0):
  24.         b = -b; bneg=-1
  25.     while (1):
  26.         quot = -(a // b)
  27.         a = a % b
  28.         a1 = a1 + quot*a2; b1 = b1 + quot*b2
  29.         if(a == 0):
  30.             return [b, a2*aneg, b2*bneg]
  31.         quot = -(b // a)
  32.         b = b % a;
  33.         a2 = a2 + quot*a1; b2 = b2 + quot*b1
  34.         if(b == 0):
  35.             return [a, a1*aneg, b1*bneg]
  36.  
  37. def invmod(a,n):
  38.     """invmod(b,n) - Compute 1/b mod n."""
  39.     return xgcd(a,n)[1] % n
  40.  
  41. p = b / xgcd(a,b)[0]
  42. d = invmod(0x010001, p - 1)
  43. m = pow(c, d, p)
  44. print ("%0256X"%m).decode("hex").lstrip("\x00")
RAW Paste Data