Why RSA must make sure that $gcd(e,φ(n))=1$ instead of $gcd(e,n)=1$?

Chinese remainder theory

cry1のWP, 大杂烩暂时挖坑 题面 from gmpy2 import * from Crypto.Util.number import * from secret import flag m = bytes_to_long(flag) R = getPrime(256) S = getPrime(512) A = getPrime(1024) N = R * S * A c = pow(m, 0x10001, N) # c = m^e mod N RA = R & A print('RSA1',hex(RA * S)) print('RSA2',hex(RA | S)) print('c', hex(c)) print('N',hex(N)) # RSA1 0x97be543979cb98c109103fa118c1c930ff13a6b2562166417021afd6e46cb0837a5cc5f4094fcea5fcc33efdfa495050e0fb8269922b3ee2d403210ed1ba339af2dc3d4e8952f0c784fcc655436cf255b98cdaf8080df47f6c28bc0bae68c713 # RSA2 0xa887aa84f3a0bd8b79ed59a7bb98d8e58a85414f85cf2ddf53ff4bd9294bfdadf7d6d6adfe7fbed55fc71b5a6bfcfe79ced27e2f41e7546a8679daf5b63dda37 # c 0x2f62fb7e7e8e27823193119f8412050ade9084ade25261a5875da23a07d5d5145e72d460697984d8aa668a25822009a4fdc85df2b208941cd3219b312f21c3c7bc4ef7aa8c18b4f91a0e815fe1892fca0f72406e571fbd0fea2c4710c601165ccd7e8a5a828721a5e2c956b732223d683d1413ef393b5f80a431c52bf9099e22b8e27daafb9d3e055242b89b5419b8925744ccf348e1bea519225af8efe7dbcc202425251039cbfe6b892a7fcf7e9d72224ea9381e3fb32ab837139af4b4112a3c7a6571c88e7d6c5db4c3f91e25edd15eb5544ef2f29a9e1bb1062ec86f1902 # N 0x58a7ff25292651e1a8d82656d64fe3b458d6e688405e85aa6c02e0c33469ad3dbaef6c6eaf8faf22f2d15e80856ab7b90a40fd50c36f7b59932bc94e6fb4fabefa87b11bf4ef74df4ccf8d254f0c6812628df3c5b3786af35e3dde9c87b462d1a565af6f100750718ccb7235174947f00cec5836765150f1680d0c58a5f9ea2473a6033c218c75664dc53377dde9386f37e1a89d77e61a716129d290c5a41f81cd3490bab6fe51f232ab27cb1ac9c8eb88e908c12109a125b7439c25b6879283a17a3467823fbb089709eb836cfd03386cc4bf186eb45401472ab0bdec605fd7 非预期解(因$N$与$rsa1$中存在公因子$S$, 直接gcd(rsa1, N) 求出S, 又因为 $S > m$ 于是 $S$ 直接当做 $N$ 使用 Q: 为什么这里的 $S$ 可以当作 $N$ 使用呢 A: 这里因为 $m$ 比 $S$ 小, 所以在模 $S$ 和模 $N$ 下加密程序( $c = m^e mod N$ )求出来的 $c$ 是一样的, 于是把 $S$ 当 $N$ 算 可以理解为因为加密公式为 $m^e mod n$ , 膜的数学小技巧为 $c = m^e mod n$ 等同于 $c＝(m mod n)^e$ , 所以在 $S＞m$ ( $s$ 是 $n$ 的一个因子) 的时候, $S$ 可以直接接做 $N$ 使用 问了些师傅 + 个人想法, 如果有错请联系我更正谢谢！ 非预期解法code from Crypto.Util.number import * from z3 import * from gmpy2 import * # from sage.all import * from math import gcd rsa1 = 0x97be543979cb98c109103fa118c1c930ff13a6b2562166417021afd6e46cb0837a5cc5f4094fcea5fcc33efdfa495050e0fb8269922b3ee2d403210ed1ba339af2dc3d4e8952f0c784fcc655436cf255b98cdaf8080df47f6c28bc0bae68c713 rsa2 = 0xa887aa84f3a0bd8b79ed59a7bb98d8e58a85414f85cf2ddf53ff4bd9294bfdadf7d6d6adfe7fbed55fc71b5a6bfcfe79ced27e2f41e7546a8679daf5b63dda37 c = 0x2f62fb7e7e8e27823193119f8412050ade9084ade25261a5875da23a07d5d5145e72d460697984d8aa668a25822009a4fdc85df2b208941cd3219b312f21c3c7bc4ef7aa8c18b4f91a0e815fe1892fca0f72406e571fbd0fea2c4710c601165ccd7e8a5a828721a5e2c956b732223d683d1413ef393b5f80a431c52bf9099e22b8e27daafb9d3e055242b89b5419b8925744ccf348e1bea519225af8efe7dbcc202425251039cbfe6b892a7fcf7e9d72224ea9381e3fb32ab837139af4b4112a3c7a6571c88e7d6c5db4c3f91e25edd15eb5544ef2f29a9e1bb1062ec86f1902 N = 0x58a7ff25292651e1a8d82656d64fe3b458d6e688405e85aa6c02e0c33469ad3dbaef6c6eaf8faf22f2d15e80856ab7b90a40fd50c36f7b59932bc94e6fb4fabefa87b11bf4ef74df4ccf8d254f0c6812628df3c5b3786af35e3dde9c87b462d1a565af6f100750718ccb7235174947f00cec5836765150f1680d0c58a5f9ea2473a6033c218c75664dc53377dde9386f37e1a89d77e61a716129d290c5a41f81cd3490bab6fe51f232ab27cb1ac9c8eb88e908c12109a125b7439c25b6879283a17a3467823fbb089709eb836cfd03386cc4bf186eb45401472ab0bdec605fd7 e = 0x10001 # S = gcd(N, rsa2) 因为 rsa1 和 N 都有相同的因子 (S == Because both rsa1 and N has same factor S. by BaakingDog S = gcd(N, rsa1) # 这里想尝试分解pq, p*q太大未遂 # print(N//S) # 非预期解 常规解法应该求出N的全部因子 (R, A) 然后d = e^-1 mod phi(N); m = c^d mod N (明文就求出来了) # 而这里因为m比s小, 所以在模n和模s下求出来的m是一样的, 于是把s当n算 d = inverse(e, S - 1) # d = e^-1 mod phi(N) 求逆元 m = pow(c, d, S) # 把s当n算 m = c^d mod N print(S > m) # True 加以验证 print(bytes.fromhex(hex(m)[2:])) # 转为字符 # print(long_to_bytes(m)) # 另一种转为字符的方式

碎碎念： rCTF一Misc题(feedback)flag就在给的链接里 但只有1/7的队伍做出来 / 令人唏嘘 / ezPVZ应该第二关需要单独修改数据且如果发现不是所修改的数据应该还原回修改前的状态，或者使用时间齿轮，不然会闪退

Crypto 写博客时的本机python环境：python 3.10 x64 cry1-babyRSA 题目附件 #!/usr/bin/env python3 import libnum import gmpy2 def main(): m = "" p = libnum.generate_prime(1024) q = libnum.generate_prime(1024) n = p * q e1 = 65537 e2 = 1145141 m = libnum.s2n(m) c1 = pow(m, e1, n) c2 = pow(m, e2, n) print(f"n = {n}") print(f"e1 = {e1}") print(f"e2 = {e2}") print(f"c1 = {c1}") print(f"c2 = {c2}") if __name__ == "__main__": main() # ------------ output ------------- # n = 11609263367794994463117283145812710043177521810736993971752031031462916890183901184704668542746877577916588155978013244385351397164066533771160861236441526284927774454246028029331726391203226023580325080150500633513024867014342350030181272221968801196510315424256352865890631054232306002238256568004250127485008008138279976475038656972273740968642332785779132654095393753232949667278798806004585797554024955342308244602767094536835410577382144435188162865642061122467384470501907391577779349252938141732012071206498806107556481558249549513041515803734342211746038126753951345855276903954190730328577080831957273691313 # e1 = 65537 # e2 = 1145141 # c1 = 8279258823057357102846768374381269167364145680055017957250521243478403606503599610855366519746944230676766499525422449675601214010991204564154995560170186683394412090168422510245266135032687364205431432451045158622417794414045719898864520112347836962316252383017549810699146506152781517871135246521405624365475969605452621085531890669372145482824845129281827033881675216546685064514926792907604133415349309151330709913454541960741984877203112442510747386406221828180805888471328964423290560512976977772551838742784356814497777401061881079781523967957560383718977490546677541952293716448514035557723329598904161762173 # c2 = 4995747575438050007737011353038705757162003396847797286289786278729187499823790079035532946676851313055563930519198963823829616599717198622635901839657079748022082189146477789049024407969208203999231434278100203042702919909473619456123328867313626560538182915794195719942071958092695261033449894563006040003298826647287929451919428024895476725340892133852628235964798488419924387986089462246202364608313134686465936926347848518960121189416319175083481701958106210362456062685045840587374473767109533027613795056920007028898921123363733374705988009798831764416119904696307107441325551226052940068337901039381485797771 解题思路 查看代码和注释掉的运行结果可知：m(密文)未知，已知e1,e2,c1,c2,n