HvAng真的太baby了

昨天被一道模运算的crypto困住了，搞完感觉很简单，但是HvAng太baby了，因为他给我推了一道baby_hint，我搞了好久，你知道这对一个新手伤害多大吗？话不多说，直接展示题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import gmpy2
import libnum
import uuid
from secret import flag
m=libnum.s2n(flag)
p=libnum.generate_prime(512)
q=libnum.generate_prime(512)
e=65537
n=p*q
hint1=pow(2023*p+2022*q,1919,n)
hint2=pow(2022*p+2023*q,9191,n)
c=pow(m,e,n)
print("hint1=",hint1)
print("hint2=",hint2)
print("n=",n)
print("c=",c)
'''
hint1= 83535799515204730191288403119559179388147974968301357768644756769205396635068662150926873512812305514469213626273460486537390422570056287512841114712846420160416446291128064734960979586229744062965998582728378025151822479630618024804808407804317029367335421715125562402059266983021662398390585435529976586654
hint2= 14402204438484882372730843813561914135941866642278909172674395293274736617425618184831446215507756031454895377588951726822765439585979555636320832177929472057402274116190878688601329765374509467243968967279090492272317903230101551317377700802837187081510381677262879617929177970455244249498674083943925477229
n= 94120719816617297967197808458007462810449143149204454740678593087096770130918870563878599847276923902207042790106345400843990455347835029220453217996810995363105274873857381469314548191574754245357568090646094043040797653858225598519876785530143007788084656262253002478643994943076851585839631209338814367691
c= 84244594789418833202484965138308516535996015903654462304986953156471594657993252593373963514364258027091543394305491354187806441313428473670956684437253991594327692679733432489342255718685303997647293213324463025120804679847465190496542879161344985402542539184706559207299026102682674060562738496314731555616

这题的思路就是把 $p$ , $q$ 之一消掉，然后运用$gcd$函数求出其中之一

原理

  1. n的因数只有 $1$,$p$,$q$,$n$
  2. 那么对于 $\forall a,b \in R,p\in N^+$ ,都有 $\gcd (ap^b,n)=p$

懂得原理之后，就可以解题了，不过对于freshman来说，模运算毕竟多了一个模，还是有点难适应的
下面是解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from Crypto.Util.number import *
from math import *
from gmpy2 import *
def fast_power(base, exponent, mod):
    result = 1
    base = base % mod
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % mod
        exponent = exponent >> 1
        base = (base * base) % mod
    return result
hint1= 83535799515204730191288403119559179388147974968301357768644756769205396635068662150926873512812305514469213626273460486537390422570056287512841114712846420160416446291128064734960979586229744062965998582728378025151822479630618024804808407804317029367335421715125562402059266983021662398390585435529976586654
hint2= 14402204438484882372730843813561914135941866642278909172674395293274736617425618184831446215507756031454895377588951726822765439585979555636320832177929472057402274116190878688601329765374509467243968967279090492272317903230101551317377700802837187081510381677262879617929177970455244249498674083943925477229
n= 94120719816617297967197808458007462810449143149204454740678593087096770130918870563878599847276923902207042790106345400843990455347835029220453217996810995363105274873857381469314548191574754245357568090646094043040797653858225598519876785530143007788084656262253002478643994943076851585839631209338814367691
c= 84244594789418833202484965138308516535996015903654462304986953156471594657993252593373963514364258027091543394305491354187806441313428473670956684437253991594327692679733432489342255718685303997647293213324463025120804679847465190496542879161344985402542539184706559207299026102682674060562738496314731555616
k = 19*101*91       #为了避免数太大，k取1919和9191的最小公倍数
a1 = fast_power(2023,k,n)*fast_power(hint1,91,n)
a2 = fast_power(2022,k,n)*fast_power(hint2,19,n)
pk = gcd(a1-a2,n)
qk = n // pk
phi = (pk-1)*(qk-1)
e = 65537
d = inverse(e,phi)
m = fast_power(c,d,n)
print(long_to_bytes(m))
#flag{ezsy_e3sy_ea4y_so_easy!!!}

这里刚开始因为解法错了，导致数太大超出pow函数范围了，所以抄了一个快速幂的函数

搞定了之后还是挺有成就感的，虽然HvAng很baby，但是还是要感谢他的知识点投喂和思路的启发

最后，如果你也认识HvAng或者他的朋友Chimedal的话，帮我线下真实他们，我将视伤害情况给予相应的报酬