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

Chinese remainder theory

根据我最近的直觉，自欺欺人是不进步的最大原因。我想大胆提出三个假设： / 最好的实践方法是任何不会让你欺骗自己的合理方法。 如果你有足够的动力，几乎任何事情都能满足上述标准。 如果你没有动力，那么几乎没有什么能满足上述标准。 通过“动机”，我有一个特定的含义。这里唯一重要的动机是对问题本身的浓厚兴趣。很多人的动机是如果他们做得好，他们就有更好的机会找到工作（我不知道这是不是真的，但是有很多人因为这个原因做CP） . 相对较少的人甚至可以获得 CP 的津贴或类似的津贴。这种动机可以作为一种次要动机，因为它给了你做 CP 而不是其他事情的理由，但这还不够。如果你只是看了史蒂夫·乔布斯或埃隆·马斯克的一段视频，其中包含一堆关于成功的通用主义，或者阅读了一些励志海报并获得了某种灵感——我认为这不会让你走得太远。对问题的兴趣在这里很重要。

保存一些推导好的结论 已知n 且p、q相邻 线索是在加密脚本中可以找到如下类似代码 p = getPrime(512) q = int(gmpy2.next_prime(p)) n = p*q 如下代码解出p、q # pq相邻 为n开方 n2 = int(gmpy2.iroot(n, 2)[0]) p = sympy.nextprime(n2) q = n//p 加以验证 print(p*q) print(n == p*q) #返回True q = sympy.nextprime()，意味着 p 和 q 是相邻的素数，非常接近，于是可以将 N 开平方根，这个数的 nextprime 就为 q $q$ 与 $phi(q^2)$ 关系 题目给出 from Crypto.Util.number import * import gmpy2 from flag import flag p=getPrime(512) q=getPrime(512) r=getPrime(512) n=p*q*r e=65537 m=bytes_to_long(flag) def Euler(x): res=0 for i in range(1,x): if gmpy2.gcd(i,x)==1: res+=1 return res P=p**3 Q=q**2 c=pow(m,e,n) print(P) print(Euler(Q)) print(c) print(n) #P = 1686761823519516525084824311416810253107853832929411677237594989001281261421956188747941222367576127569696216513071075733130132251383529469095077597202999362675041210639065389821237728348981344440193122126487447235175127680730304754656661704596111547454161716607787386914764780833658069534913186485846587027674567133467341836048413431174183101579802349498153899249182793495245916757355079598668221097821452488627067390724198617676379698358212167618567704428433303 #EQ = 54800501457630149544580145188029519076092032026436445384163914536965196942938808746487258773679836358732387355329080483568564046906919385574994390974732491368590525875801103056613954297623835159311237599961507385582029709732950222118171961946571285930711702624160354541459438994349318149872111029043942485620 #c = 568846080701555049788706647255668980211679838950729382006912035332305772256748203239331545262283165739670330060735508231578298253855583985677482008855909565463834639005910652510802915373310537390293061001384655286359323437737989289787972131460392977341024828530868508329336263146882773903176326250063921456707975853839017504122823304303509269793133132036479219404842827556015566627129747816769486873563843578029479179692030808518925753268233301452280242586076493 #n = 1069981867450019752454430625015273180922733107799929958042241890002915414684562764186875387471850290817321430141222917656674447229697676236077201897275059270515637506529666384968535578683380559782336910645306992981172862940944536463561840412558764760962107958365575095435157363812028759723055357681895134974760386884254380189603418912937553755099672511307377054933171384741715642510754214768859689909974996095149155241791151425031489280537907842378844226410097051 解出q Euler(q^2) = q * (q-1)，那么 q-1 < sqrt(Euler(q^2)) < q.(已翻译)

在acm被称为快速幂(平方求幂) 在ctf中也被称为 $montecarlo$ 先说幂运算的朴素做法，在数学中，重复连乘的运算叫做乘方，乘方的结果称为 幂 ${\displaystyle n}$ 个相同的数 ${\displaystyle b}$ 连续相乘 [公式] // c++ version #include <iostream> int b, n, sum; // 仅作演示, 实际应该使用python或高精度防止爆int int main() { std::cin >> b >> n; if (n == 0) { //对0次幂特判 std::cout << 1; return 0; } sum = b, n = n - 1; while (n --) { sum *= b; } for (int sum) std::cout << sum; return 0; } 让我们先来思考一个问题：7的10次方，怎样算比较快？ 方法1：上述提到的朴素算法, 来计算 $7 *7=49$，$49* 7=343$ / 这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。 / 方法2：先算7的5次方，即$7 *7* 7 *7* 7$，再算它的平方，共进行了5次乘法。 / 方法3：先算7 *7得49，则7的5次方为$49* 49 \* 7$，再算它的平方，共进行了4次乘法。

构造+贪心(R1000) / 剩余24h A. Find Amir / # 有n个地点，每来往i，j两个地点就花费（i+j）mod（n+1），问遍历所有地点的最低花费 # 当i+j==n+1每两地花费最小，如1, n; 2，n-1 # 只需以1->n->2->n-1->3...这样的顺序花费就最小 n = int(input()) res = 0 # res = (n-1)/2 if n & 1: # n is odd res = (n - 1) >> 1 else: res = (n >> 1) - 1 print(res) by: 易如鱼 & aYi_7 & 张少锋 / 分析：由于花费是要（i+j）mod（n+1），则尽可能使每段路程的i+j都接近n+1，通过样例中n=10的情况，不难发现解法。从1到n，花费为0(11%11 = 0)；从n走到2，花费为1(12%11=1)；从2到n-1，花费为0；从n-1到3，花费为1;从3到n-2…这样循环往复，每次向右走花费为零，向左走花费为1。据此不难写出通项公式：cost =（n-1）mod 2。

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应该第二关需要单独修改数据且如果发现不是所修改的数据应该还原回修改前的状态，或者使用时间齿轮，不然会闪退

n和Q求最大公约数拿到q，P直接开立方拿到p，n整除p和q拿到r 或者求解q时可以 # Eq = Euler(Q) = Euler(q**2) 求q-> sqrt(Euler(q**2)) + 1 = q # EQQ = gmpy2.iroot(Eq, 2)[0] # 求平方根 # q = EQQ + 1 Euler对于任意 互质 的整数a和b有性质f(a b) = f(a) ⋅ f(b) / 题面 from Crypto.Util.number import * import gmpy2 from flag import flag p=getPrime(512) q=getPrime(512) r=getPrime(512) n=p*q*r e=65537 m=bytes_to_long(flag) def Euler(x): res=0 for i in range(1,x): if gmpy2.gcd(i,x)==1: res+=1 return res P=p**3 Q=q**2 c=pow(m,e,n) print(P) print(Euler(Q)) print(c) print(n) #P = 1686761823519516525084824311416810253107853832929411677237594989001281261421956188747941222367576127569696216513071075733130132251383529469095077597202999362675041210639065389821237728348981344440193122126487447235175127680730304754656661704596111547454161716607787386914764780833658069534913186485846587027674567133467341836048413431174183101579802349498153899249182793495245916757355079598668221097821452488627067390724198617676379698358212167618567704428433303 #Eq = 54800501457630149544580145188029519076092032026436445384163914536965196942938808746487258773679836358732387355329080483568564046906919385574994390974732491368590525875801103056613954297623835159311237599961507385582029709732950222118171961946571285930711702624160354541459438994349318149872111029043942485620 #c = 568846080701555049788706647255668980211679838950729382006912035332305772256748203239331545262283165739670330060735508231578298253855583985677482008855909565463834639005910652510802915373310537390293061001384655286359323437737989289787972131460392977341024828530868508329336263146882773903176326250063921456707975853839017504122823304303509269793133132036479219404842827556015566627129747816769486873563843578029479179692030808518925753268233301452280242586076493 #n = 1069981867450019752454430625015273180922733107799929958042241890002915414684562764186875387471850290817321430141222917656674447229697676236077201897275059270515637506529666384968535578683380559782336910645306992981172862940944536463561840412558764760962107958365575095435157363812028759723055357681895134974760386884254380189603418912937553755099672511307377054933171384741715642510754214768859689909974996095149155241791151425031489280537907842378844226410097051 $gcd$ 方法 from Crypto.Util.number import * e = 65537 r = 12142261002625479270959358223863571062295429117378994112396394259314721874267081158944354513358164889564741712782226613341612447412750073385958464420872713 c = 568846080701555049788706647255668980211679838950729382006912035332305772256748203239331545262283165739670330060735508231578298253855583985677482008855909565463834639005910652510802915373310537390293061001384655286359323437737989289787972131460392977341024828530868508329336263146882773903176326250063921456707975853839017504122823304303509269793133132036479219404842827556015566627129747816769486873563843578029479179692030808518925753268233301452280242586076493 n = 1069981867450019752454430625015273180922733107799929958042241890002915414684562764186875387471850290817321430141222917656674447229697676236077201897275059270515637506529666384968535578683380559782336910645306992981172862940944536463561840412558764760962107958365575095435157363812028759723055357681895134974760386884254380189603418912937553755099672511307377054933171384741715642510754214768859689909974996095149155241791151425031489280537907842378844226410097051 # p = gmpy2.iroot(P, 3)[0] # 开3次方根 p = 11903771663059518341912645066042582267678745214691121272332269847512624178064427789028954264701292914161793272471217879550653909080475237446747964043276487 # q = gmpy2.gcd(n,Eq) q = 7402736079155473279000574596031490410671021795687853893698348179857428763438305848933328416647633118223876785823588566614584124350907811192587130096357221 phi = (q - 1) * (p - 1) * (r - 1) # phi = (q - 1) * (p - 1) # n = q * p d = pow(e, -1, phi) # 求逆元 d = e**-1 mod phi m = pow(c, d, n) print(long_to_bytes(m)) 拿到q p r (n的三个因子) 后也可以只用q p (不用r) 构造出新的phi, d和n来解密(数学底力不足，有的题不能这样操作，原因暂时未知，挖坑先) from Crypto.Util.number import * q = 7402736079155473279000574596031490410671021795687853893698348179857428763438305848933328416647633118223876785823588566614584124350907811192587130096357221 p = 11903771663059518341912645066042582267678745214691121272332269847512624178064427789028954264701292914161793272471217879550653909080475237446747964043276487 e = 65537 r = 12142261002625479270959358223863571062295429117378994112396394259314721874267081158944354513358164889564741712782226613341612447412750073385958464420872713 c = 568846080701555049788706647255668980211679838950729382006912035332305772256748203239331545262283165739670330060735508231578298253855583985677482008855909565463834639005910652510802915373310537390293061001384655286359323437737989289787972131460392977341024828530868508329336263146882773903176326250063921456707975853839017504122823304303509269793133132036479219404842827556015566627129747816769486873563843578029479179692030808518925753268233301452280242586076493 n = 1069981867450019752454430625015273180922733107799929958042241890002915414684562764186875387471850290817321430141222917656674447229697676236077201897275059270515637506529666384968535578683380559782336910645306992981172862940944536463561840412558764760962107958365575095435157363812028759723055357681895134974760386884254380189603418912937553755099672511307377054933171384741715642510754214768859689909974996095149155241791151425031489280537907842378844226410097051 # phi = (q - 1) * (p - 1) * (r - 1) phi = (q - 1) * (p - 1) n = q * p d = pow(e, -1, phi) m = pow(c, d, n) print(long_to_bytes(m)) $sqrt(Eq)$ #by sangge’s code from Crypto.Util.number import * import gmpy2 import binascii import hashlib def Euler(x): res = 0 for i in range(1, x): if gmpy2.gcd(i, x) == 1: res += 1 return res # 16进制转字符串 def hex_to_str1(s): s = binascii.unhexlify(s) # ASCII 码转换函数 # unhexlify()传入的参数也可以是b'xxxx'(xxxx要符合16进制特征) return s.decode('utf-8') # s的类型是bytes类型，用encode()方法转化为str类型(去除b'') P = 1686761823519516525084824311416810253107853832929411677237594989001281261421956188747941222367576127569696216513071075733130132251383529469095077597202999362675041210639065389821237728348981344440193122126487447235175127680730304754656661704596111547454161716607787386914764780833658069534913186485846587027674567133467341836048413431174183101579802349498153899249182793495245916757355079598668221097821452488627067390724198617676379698358212167618567704428433303 EQ = 54800501457630149544580145188029519076092032026436445384163914536965196942938808746487258773679836358732387355329080483568564046906919385574994390974732491368590525875801103056613954297623835159311237599961507385582029709732950222118171961946571285930711702624160354541459438994349318149872111029043942485620 c = 568846080701555049788706647255668980211679838950729382006912035332305772256748203239331545262283165739670330060735508231578298253855583985677482008855909565463834639005910652510802915373310537390293061001384655286359323437737989289787972131460392977341024828530868508329336263146882773903176326250063921456707975853839017504122823304303509269793133132036479219404842827556015566627129747816769486873563843578029479179692030808518925753268233301452280242586076493 n = 1069981867450019752454430625015273180922733107799929958042241890002915414684562764186875387471850290817321430141222917656674447229697676236077201897275059270515637506529666384968535578683380559782336910645306992981172862940944536463561840412558764760962107958365575095435157363812028759723055357681895134974760386884254380189603418912937553755099672511307377054933171384741715642510754214768859689909974996095149155241791151425031489280537907842378844226410097051 e = 65537 p = gmpy2.iroot(P, 3)[0] # Euler对于任意 互质 的整数a和b有性质f ( a b ) = f ( a ) ⋅ f ( b ) Eq = gmpy2.iroot(EQ, 2)[0] # 求平方根 q = Eq + 1 r = n//p//q # 求整数除法 phi_n = (p - 1) * (q - 1) * (r - 1) # 求欧拉函数 d = gmpy2.invert(e, phi_n) # 求逆元 m = pow(c, d, n) # 求模幂 # print(m) flag = hex_to_str1(hex(m)[2:]) # 不会附带 b'' 与下方转换类似(# 转化为16进制 后去掉前面的0x 后转化为str类型) # flag = long_to_bytes(m) # 会附带 b'' 可以像上面一样再转一次str print(flag[5:-1]) # 去掉前后的flag{} ,下面继续进行题意要求的md5加密 hash = hashlib.md5() # md5加密 hash.update(flag[5:-1].encode('utf-8')) # encode()方法将str类型转化为bytes类型 print("flag{" + hash.hexdigest() + "}") # hexdigest()方法将bytes类型转化为str类型 ![q的推导.png]]

基本原理 公钥与私钥的产生 随机选择两个不同大质数 $p$ 和 $q$，计算 $N=p\times q$ 根据欧拉函数，求得 $\phi(N)=\phi(p)\phi(q)=(p-1)(q-1)$ 选择一个小于 $\phi(N)$ 的整数 $e$，使 $e$ 和 $\phi(N)$ 互质。并求得 $e$ 关于 $\phi(N)$ 的模反元素，命名为 $d$，有 $ed \equiv 1 \pmod{\phi(N)}$ 将 $p$ 和 $q$ 的记录销毁 此时，$(N,e)$ 是公钥，$(N,d)$ 是私钥。