strangekey
問題
This key seems strange, doesn't it?
strange_key.zip
メモ
解法
- key.pubにはBEGIN PUBLIC KEYが含まれているのでPEMのRSAキー
DER形式に変換してからdumpasn1でインスペクト
% openssl rsa -outform DER -in key.pub -out key.pub.der -pubin -pubout writing RSA key % dumpasn1 -a key.der 0 545: SEQUENCE { 4 13: SEQUENCE { 6 9: OBJECT IDENTIFIER rsaEncryption (1 2 840 113549 1 1 1) 17 0: NULL : } 19 526: BIT STRING, encapsulates { 24 521: SEQUENCE { 28 257: INTEGER : 00 9A D0 6B C9 71 36 3A 84 B5 93 6F F3 65 51 86 : 84 B8 98 66 C7 65 57 EF 6C AA 31 08 EE 1D 15 AC : D8 7C 01 B6 EF 4B 9E 9F 4E CC AC FE 21 93 7F E6 : 6C 7F 86 DB 7A 28 B5 B3 F1 2A 0F 02 21 8B 8C 89 : 78 96 3B 82 C4 A7 5F 26 0F C6 AD 6A B2 27 5D 57 : D8 A2 CA E8 79 33 9D 22 52 D6 DA 68 A7 02 C0 17 : 47 85 55 46 37 E7 03 E8 ED 47 32 FE 2E 19 B2 AA : CF 11 36 46 D5 19 86 C8 81 71 D0 2E 49 13 C3 AE : 3A 6A 3F C9 F9 8A 58 B4 45 A3 A9 AE 23 57 E3 D5 : 37 F6 AF 90 EF 78 CB 9B 7B 6A 96 34 45 2A 02 92 : B1 45 7F 61 DA 82 29 48 58 3A 29 FE 5C A3 1D 45 : B3 53 CD C7 56 E1 01 08 4E E6 C9 64 25 B8 6E 1D : A6 2D 65 7A 1D 59 C2 70 F2 CB C0 AD B4 64 46 F8 : AD FB CD 7C 2D BC 7B 5E 77 79 50 5C B7 79 A8 2E : 05 A9 A1 4E 95 77 45 B0 92 B7 E6 44 D7 0E A8 7E : D8 03 00 21 DC CD 36 7D 97 C0 6C DE ED BF 82 AF : 77 289 256: INTEGER : 34 0F 75 3C B5 0C 4D F1 64 3C 85 A7 08 EF FB C0 : 70 E1 E3 C3 E6 B6 BD 8B 03 EE E8 28 1A 88 4A D0 : 33 08 69 F6 01 6E 43 4B 00 F8 7B 2C CF 0D C2 2D : B8 EE BC 67 78 AF 81 B8 80 C9 38 63 05 F7 C6 DF : DF 2F A5 19 3C 96 63 C5 3F E0 7A AE 46 11 5C 08 : 7F C9 4F 83 C7 77 B7 FE BA AB B2 39 97 98 5D 6F : FB F8 FB 06 AD 61 76 E5 4A 9A 75 F6 37 E3 FB 67 : C8 14 DE 29 8A F0 A5 16 50 60 7C 74 9A 56 18 E4 : 46 1D 25 F8 D4 60 86 D0 FF DC 88 05 C3 0B B4 29 : 82 6F A6 7C C2 87 58 3E 95 14 23 81 94 A7 14 05 : D5 74 ED B5 72 2F B8 FA 92 C2 C6 E9 A9 F6 1D A1 : 52 8B 16 5C DB 3D 86 60 8F CF 3B A3 F2 B3 66 54 : F2 35 EA C6 B5 25 94 FE 07 04 F9 46 D5 47 47 E7 : F8 75 4B 80 FF 9E A4 C3 97 83 52 75 56 4D 62 E5 : D6 94 53 8A 7E 44 B4 A8 2B 7F E9 26 B8 F2 D6 0C : 50 F6 28 6C 41 65 FC 8D 9D D5 19 CC D6 D9 52 49 : } : } : } 0 warnings, 0 errors.
- 値は$n, e$の順。$e$が異様に大きい。$d$が小さいことを疑う。
- $d$が小さいといえばWienerのLow Private Exponent攻撃
Wiener攻撃で$n$を素因数分解する
1 from fractions import Fraction 2 3 def continued_fraction(N, e): 4 result = [] 5 (a, b) = (e, N) 6 while b != 0: 7 n = a / b 8 result.append(n) 9 (a, b) = (b, a % b) 10 return result 11 12 def extract_candidates(N, e): 13 cf = continued_fraction(N, e) 14 for i in range(1, len(cf) + 1): 15 kd = Fraction(0) 16 for x in cf[1:i][::-1]: 17 kd = 1/(kd + x) 18 yield (kd.numerator, kd.denominator) 19 20 def bisect(left, right, cond_le): 21 # [left, right] 22 while left <= right: 23 if left == right: 24 return left 25 mid = (left + right) / 2 26 if cond_le(mid): 27 right = mid 28 else: 29 left = mid + 1 30 return None 31 32 33 def sqrt_ceil(n): 34 return bisect(0, n, lambda x: n <= x*x) 35 36 def solve_quadratic_equation(a, b): 37 m = sqrt_ceil(b) 38 p = bisect(0, m, lambda x: x*x-a*x+b <= 0) 39 q = bisect(m, b, lambda x: x*x-a*x+b >= 0) 40 if p * q != b: 41 return None 42 else: 43 return (p, q) 44 45 def wiener(n, e): 46 for (k, d) in extract_candidates(n, e): 47 if k == 0: 48 continue 49 ed = e*d 50 if (ed - 1) % k != 0: 51 continue 52 phin = (e*d - 1) / k 53 result = solve_quadratic_equation(n - phin + 1, n) 54 if result is None: 55 continue 56 (p, q) = result 57 return (p, q) 58 59 n=0x009AD06BC971363A84B5936FF365518684B89866C76557EF6CAA3108EE1D15ACD87C01B6EF4B9E9F4ECCACFE21937FE66C7F86DB7A28B5B3F12A0F02218B8C8978963B82C4A75F260FC6AD6AB2275D57D8A2CAE879339D2252D6DA68A702C0174785554637E703E8ED4732FE2E19B2AACF113646D51986C88171D02E4913C3AE3A6A3FC9F98A58B445A3A9AE2357E3D537F6AF90EF78CB9B7B6A9634452A0292B1457F61DA822948583A29FE5CA31D45B353CDC756E101084EE6C96425B86E1DA62D657A1D59C270F2CBC0ADB46446F8ADFBCD7C2DBC7B5E7779505CB779A82E05A9A14E957745B092B7E644D70EA87ED8030021DCCD367D97C06CDEEDBF82AF77 60 e=0x340F753CB50C4DF1643C85A708EFFBC070E1E3C3E6B6BD8B03EEE8281A884AD0330869F6016E434B00F87B2CCF0DC22DB8EEBC6778AF81B880C9386305F7C6DFDF2FA5193C9663C53FE07AAE46115C087FC94F83C777B7FEBAABB23997985D6FFBF8FB06AD6176E54A9A75F637E3FB67C814DE298AF0A51650607C749A5618E4461D25F8D46086D0FFDC8805C30BB429826FA67CC287583E9514238194A71405D574EDB5722FB8FA92C2C6E9A9F61DA1528B165CDB3D86608FCF3BA3F2B36654F235EAC6B52594FE0704F946D54747E7F8754B80FF9EA4C397835275564D62E5D694538A7E44B4A82B7FE926B8F2D60C50F6286C4165FC8D9DD519CCD6D95249 61 (p, q) = wiener(n, e) 62 print (p, q)
% python solve.py (136843338254631672534659189135371681290783474140056458861301409707406815414824614314321502261447027492769233336717326478385896821172868473367268413764707770686088535065019461169464733561856977831760838812501087480519235700399042137994601024850764405186214551542870149555178473381580700736878071050646652178263L, 142816416645686751226743514899552666619180089970148655676361181676027392698053864926419045489167610369468551223969631942233315097402533730703654525823553590709168604179184191278874751567402840950857003037624831713834284921309309694505448004548204512718509760509935143346448809245197854321538917598614997282017L)
PEMの秘密鍵を再構成して
% ruby generate-rsakey.rb 136843338254631672534659189135371681290783474140056458861301409707406815414824614314321502261447027492769233336717326478385896821172868473367268413764707770686088535065019461169464733561856977831760838812501087480519235700399042137994601024850764405186214551542870149555178473381580700736878071050646652178263 142816416645686751226743514899552666619180089970148655676361181676027392698053864926419045489167610369468551223969631942233315097402533730703654525823553590709168604179184191278874751567402840950857003037624831713834284921309309694505448004548204512718509760509935143346448809245197854321538917598614997282017 6572014461210452833553570645607418497915740079671227862214176405241505237634123479550757805182154443698244682496187953825017363957243329733918453584299477453836996235029166341622072928827953881972121574093091992668393975346210868927585091064703218209811975165343344148007759136691858233226806203903249126793360723800628442929187022808474092981807451624719040814168886136164561208469621676036021438848856077031926430535901058936732877592997643830349784412725845096429716633949006572349334459605051868484874413541578878960431229814279803252922853695497013440291707507633031265667716336096762119080078125766820918547017 -----BEGIN RSA PRIVATE KEY----- MIIEVAIBAAKCAQEAmtBryXE2OoS1k2/zZVGGhLiYZsdlV+9sqjEI7h0VrNh8 AbbvS56fTsys/iGTf+Zsf4bbeii1s/EqDwIhi4yJeJY7gsSnXyYPxq1qsidd V9iiyuh5M50iUtbaaKcCwBdHhVVGN+cD6O1HMv4uGbKqzxE2RtUZhsiBcdAu SRPDrjpqP8n5ili0RaOpriNX49U39q+Q73jLm3tqljRFKgKSsUV/YdqCKUhY Oin+XKMdRbNTzcdW4QEITubJZCW4bh2mLWV6HVnCcPLLwK20ZEb4rfvNfC28 e153eVBct3moLgWpoU6Vd0WwkrfmRNcOqH7YAwAh3M02fZfAbN7tv4KvdwKC AQA0D3U8tQxN8WQ8hacI7/vAcOHjw+a2vYsD7ugoGohK0DMIafYBbkNLAPh7 LM8Nwi247rxneK+BuIDJOGMF98bf3y+lGTyWY8U/4HquRhFcCH/JT4PHd7f+ uquyOZeYXW/7+PsGrWF25UqadfY34/tnyBTeKYrwpRZQYHx0mlYY5EYdJfjU YIbQ/9yIBcMLtCmCb6Z8wodYPpUUI4GUpxQF1XTttXIvuPqSwsbpqfYdoVKL FlzbPYZgj887o/KzZlTyNerGtSWU/gcE+UbVR0fn+HVLgP+epMOXg1J1Vk1i 5daUU4p+RLSoK3/pJrjy1gxQ9ihsQWX8jZ3VGczW2VJJAj0IBRyJsN0ur3Vo yS8oe6Yc1l2hR3BAzutDmz5k4L8vp4miXJaQDuYqzOfQCkBp/NLpn9JpceGj SpjZmnd5AoGBAMLfEucbIclJ19w5qASPp1G1ObYLW8WdQ71knMe3wZ0992zQ /anwkPUgnfrQXLwAWz+8cHSzEfBuoIH4F5KcDfnR0UZRO4mo+/0krn3Rzk6q cPvEpyJWTHOR3Lb86tvzIDNjq848P4xJBX98mOfNtqDoCWYGMrd7VazfZLUL u89XAoGBAMtgmJP6imN0xCzFZ8hGZYUmPXgvAuXnZNzZHB6aZGIWvDmGUUYv VgWJWZDD7n87bRCxGAUs3lzuubzoAkuBv3gsEdKLAPp2QPi6f0E+uYuJQbBS FAgwwSHfVIwQ0y+60UwU4Jmjz7RASxUOQU5bD6BMu7nWL4JqA3jYhhzyFazh Aj0IBRyJsN0ur3VoyS8oe6Yc1l2hR3BAzutDmz5k4L8vp4miXJaQDuYqzOfQ CkBp/NLpn9JpceGjSpjZmnd5Aj0IBRyJsN0ur3VoyS8oe6Yc1l2hR3BAzutD mz5k4L8vp4miXJaQDuYqzOfQCkBp/NLpn9JpceGjSpjZmnd5AoGASySxj/P7 GvGltgrUSZq0TQJ4i/FtzfNPXwNGz1bbenclBe9d6PwFPz4X8DchN2PZRSzf 3etALVKa8Tvnfe1RYQNUBBITE8ku7ApVx1laM0mAz9ZLKKU6qQSq04UNcnbj vlJn046VDPxDOxESAECvXHxEFFNzqCWhgojlntaGKNo= -----END RSA PRIVATE KEY-----
復号してフラグを得る。
% openssl rsautl -decrypt -in flag.enc -out flag -inkey key.pem % cat flag ADCTF_W13n3r5_4774ck_15_V3RY_fun