Signin

源码：

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 secret import flag


m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
c = pow(m,e,n)
pq = (p-1)*(q-2)
qp = (q-1)*(p-2)
p_q = p + q


print(f"{c = }")
print(f"{pq = }")
print(f"{qp = }")
print(f"{n = }")
print(f"{p_q = }")
'''
c = 5654386228732582062836480859915557858019553457231956237167652323191768422394980061906028416785155458721240012614551996577092521454960121688179565370052222983096211611352630963027300416387011219744891121506834201808533675072141450111382372702075488292867077512403293072053681315714857246273046785264966933854754543533442866929316042885151966997466549713023923528666038905359773392516627983694351534177829247262148749867874156066768643169675380054673701641774814655290118723774060082161615682005335103074445205806731112430609256580951996554318845128022415956933291151825345962528562570998777860222407032989708801549746
pq = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687154230787854196153067547938936776488741864214499155892870610823979739278296501074632962069426593691194105670021035337609896886690049677222778251559566664735419100459953672218523709852732976706321086266274840999100037702428847290063111455101343033924136386513077951516363739936487970952511422443500922412450462
qp = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687077087914198877794354459669808240133383828356379423767736753506794441545506312066344576298453957064590180141648690226266236642320508613544047037110363523129966437840660693885863331837516125853621802358973786440314619135781324447765480391038912783714312479080029167695447650048419230865326299964671353746764860
n = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687534959910892789661065614807265825078942931717855566686073463382398417205648946713373617006449901977718981043020664616841303517708207413215548110294271101267236070252015782044263961319221848136717220979435486850254298686692230935985442120369913666939804135884857831857184001072678312992442792825575636200505903
p_q = 279533706577501791569740668595544511920056954944184570513187478007551195831693428589898548339751066551225424790534556602157835468618845221423643972870671556362200734472399328046960316064864571163851111207448753697980178391430044714097464866523838747053135392202848167518870720149808055682621080992998747265496
'''

分析

已经知道c, n，只需要再求出 d 即可
∵e⋅d≡1mod  ϕ(n)\because e\cdot d \equiv 1 \mod \phi(n)
phi(n)=(p−1)(q−1)=pq−(p+q)+1phi(n) = (p-1)(q-1) = pq - (p+q) +1
而p_q已经给出了p+q，直接就可以求出ϕ(n)\phi(n)了
pq, qp是来混淆视听的…

exp

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import *

c = 5654386228732582062836480859915557858019553457231956237167652323191768422394980061906028416785155458721240012614551996577092521454960121688179565370052222983096211611352630963027300416387011219744891121506834201808533675072141450111382372702075488292867077512403293072053681315714857246273046785264966933854754543533442866929316042885151966997466549713023923528666038905359773392516627983694351534177829247262148749867874156066768643169675380054673701641774814655290118723774060082161615682005335103074445205806731112430609256580951996554318845128022415956933291151825345962528562570998777860222407032989708801549746
n = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687534959910892789661065614807265825078942931717855566686073463382398417205648946713373617006449901977718981043020664616841303517708207413215548110294271101267236070252015782044263961319221848136717220979435486850254298686692230935985442120369913666939804135884857831857184001072678312992442792825575636200505903
p_q = 279533706577501791569740668595544511920056954944184570513187478007551195831693428589898548339751066551225424790534556602157835468618845221423643972870671556362200734472399328046960316064864571163851111207448753697980178391430044714097464866523838747053135392202848167518870720149808055682621080992998747265496

phi = n-p_q+1
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

ez_hash

源码：

1
2
3
4
5
6
7
8
from hashlib import sha256
from secret import flag, secrets

assert flag == b'moectf{' + secrets + b'}'
assert secrets[:4] == b'2100' and len(secrets) == 10
hash_value = sha256(secrets).hexdigest()
print(f"{hash_value = }")
# hash_value = '3a5137149f705e4da1bf6742e62c018e3f7a1784ceebcb0030656a2b42f50b6a'

分析

由题目描述“想要得到我的联系方式就努力解出下面的题目吧。“可知，secrets全部是数字

assert secrets[:4] == b'2100' and len(secrets) == 10
secrets前4位是2100，长度为10

遍历 1~1000000 的数字i, 并填充满足长度为6(这样加上前面的4位合起来就是10位)，合并起来进行sha256加密，若加密结果与hash_value相同，则说明此时的secrets正确

zfill()
作用对象和返回值类型都是字符串

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
from hashlib import *
from tqdm import *

hash_value = '3a5137149f705e4da1bf6742e62c018e3f7a1784ceebcb0030656a2b42f50b6a'
for i in trange(1, 1000000):
    secret = b'2100' + str(i).zfill(6).encode()
    temp = sha256(secret).hexdigest()
    if temp == hash_value:
        flag = b'moectf{' + secret + b'}'
        break
           
print(f"结果是:  {flag} ")

Big and small

源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
from secret import flag
from Crypto.Util.number import*
m = long_to_bytes(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 3
c = pow(m,e,n)
'''
c = 150409620528288093947185249913242033500530715593845912018225648212915478065982806112747164334970339684262757
e = 3
n = 20279309983698966932589436610174513524888616098014944133902125993694471293062261713076591251054086174169670848598415548609375570643330808663804049384020949389856831520202461767497906977295453545771698220639545101966866003886108320987081153619862170206953817850993602202650467676163476075276351519648193219850062278314841385459627485588891326899019745457679891867632849975694274064320723175687748633644074614068978098629566677125696150343248924059801632081514235975357906763251498042129457546586971828204136347260818828746304688911632041538714834683709493303900837361850396599138626509382069186433843547745480160634787
'''

分析

一眼小明文攻击

c≡me(modn)c \equiv m^e \pmod n

当e非常小，p, q非常大时，me<<nm^e << n
取模后保留了原型。类似于 5mod  100000=55 \mod 100000 = 5
此时

c=mec = m^e

使用iroot函数对 c 开 e 次方就能得到 m

exp

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
from gmpy2 import *

c = 150409620528288093947185249913242033500530715593845912018225648212915478065982806112747164334970339684262757
e = 3
n = 20279309983698966932589436610174513524888616098014944133902125993694471293062261713076591251054086174169670848598415548609375570643330808663804049384020949389856831520202461767497906977295453545771698220639545101966866003886108320987081153619862170206953817850993602202650467676163476075276351519648193219850062278314841385459627485588891326899019745457679891867632849975694274064320723175687748633644074614068978098629566677125696150343248924059801632081514235975357906763251498042129457546586971828204136347260818828746304688911632041538714834683709493303900837361850396599138626509382069186433843547745480160634787

m = iroot(c, e)[0]
print(long_to_bytes(m))

baby_equation

源码：

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
from secret import flag

l = len(flag)
m1, m2 = flag[:l//2], flag[l//2:]
a = bytes_to_long(m1)
b = bytes_to_long(m2)
k = 0x2227e398fc6ffcf5159863a345df85ba50d6845f8c06747769fee78f598e7cb1bcf875fb9e5a69ddd39da950f21cb49581c3487c29b7c61da0f584c32ea21ce1edda7f09a6e4c3ae3b4c8c12002bb2dfd0951037d3773a216e209900e51c7d78a0066aa9a387b068acbd4fb3168e915f306ba40
assert ((a**2 + 1)*(b**2 + 1) - 2*(a - b)*(a*b - 1)) == 4*(k + a*b)

分析

对于给出的复杂断言式，首先将a，b 都移到同一边

((a∗∗2+1)∗(b∗∗2+1)−2∗(a−b)∗(a∗b−1))−4∗a∗b=4∗k((a**2 + 1)*(b**2 + 1) - 2*(a - b)*(a*b - 1)) - 4*a*b= 4*k

用sagemath对等式左边factor

分解一个表达式的流程

  1. 声明变量
    a, b = var(‘a, b’)
  2. 定义表达式
    f = …
  3. 分解表达式
    f.factor()

分解数据
直接factor(…)


发现是一个平方式，那么对左右两边同时开方

(a+1)∗(b−1)=2k(a+1) * (b-1) = 2 \sqrt k

再次使用sagemath对 2k2 \sqrt k 做factor，找出2k2 \sqrt k的所有因子，将这些因子分为两部分，每部分的乘积分别对应(a+1), (b-1)

这样就可以求出a,b的值，当 long_to_bytes(a) 包含flag头时 ， 就说明这时的因子分配是正确的

对 2k2 \sqrt k 做factor:

  1. 先factor(k)
  2. 那么 k\sqrt k 就是对它开根， factor(k) 全是偶次幂， 直接幂数都除以2就行
    factor(k)(\sqrt k) = 2^3 * 3^2 * 31^1 * 61^1 * 223^1 * 4013^1 * 281317^1 * 4151351^1 * 339386329^1 * 370523737^1 * 5404604441993^1 * 26798471753993^1 * 25866088332911027256931479223^1 * 64889106213996537255229963986303510188999911^1
  3. 2k2 \sqrt k 就是在因子中加上一个2

整理一下，
factors = [2, 2, 2, 2, 3, 3, 31, 61 , 223, 4013, 281317, 4151351, 339386329, 370523737, 5404604441993, 26798471753993, 25866088332911027256931479223, 64889106213996537255229963986303510188999911]

那么怎么组合因子，使得一部分乘积对应(a+1), 剩下的乘积对应(b-1)
这里我们采用了二进制数作为幂次，举一个简单的例子：
factor(24) = [2, 2, 2, 3] , 有4个因子

1
2
3
4
5
6
product = prod(factor)  # 所有因子的乘积，其实就等于24
for i in range(1 << 4):    # 1左移4位，相当于 2 ^ 4 ，因为每个小因子要么使用，幂数为1，要么不使用，幂数为0，一共4个小因子， 那么一共有2*2*2*2 = 2^4 种情况
  temp = bin(int(i))[2:].zfill(4)  # 0~2^4 每个数转成二进制，且要保证二进制位数为4  bin()转换后以 0b 开头，所以只取0b之后的纯二进制
  one_factor = prod([factor[j] ** (int(temp[j], 2)) for j in range(4)])
  # 假设此时遍历到了2^2, 对应的temp = 0100, 那么 one_factor = 2^0 * 2^1 * 2^0 * 3^0
  other_factor = product // one_factor # 计算此时的另一个因子

prod()
属于numpy库， 计算列表中所有元素的乘积, 返回类型是个奇奇怪怪的啥玩意儿，所以有时候需要int(prod(…))

factor(2k2 \sqrt k)有18个小因子， 就是 2^18 种情况，按照上面的方法求出满足条件的因子即可
需要注意的是，求出来的因子并不是 a, b, 而是(a+1) , (b-1) , 所以要做相应的处理后再long_to_bytes

exp1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from numpy import prod
from tqdm import *

factors = [2, 2, 2, 2, 3, 3, 31, 61 , 223,  4013,  281317,  4151351,  339386329,  370523737, 5404604441993, 26798471753993, 25866088332911027256931479223, 64889106213996537255229963986303510188999911]
product = prod(factors)

for i in trange(1<<18):
    tmp = bin(int(i))[2:].zfill(18)
    adding_one = prod([factors[j] ** (int(tmp[j], 2)) for j in range(18)])
    a = adding_one - 1
    if a>0:  # 当i=0时，adding_one=1, a=0, long_to_bytes(a)会报错
      try:
          m1 = long_to_bytes(a)
          if b'moe' in m1:
              b = product // adding_one + 1
              flag = m1 + long_to_bytes(b)
              print(flag)
              break
      except OverflowError:  # 因为是遍历了所以情况，所以某种因子情况下a或b可能非常非常大，超出了long_to_bytes能处理的范围。使用except  OverflowError 跳过报这种错的情况
          pass

exp2

更简单粗暴的情况，直接忽略所有报错，只找flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
from numpy import prod
from tqdm import *

factors = [2, 2, 2, 2, 3, 3, 31, 61 , 223,  4013,  281317,  4151351,  339386329,  370523737, 5404604441993, 26798471753993, 25866088332911027256931479223, 64889106213996537255229963986303510188999911]
product = prod(factors)

for i in trange(1<<18):
    tmp = bin(int(i))[2:].zfill(18)
    adding_one = prod([factors[j] ** (int(tmp[j], 2)) for j in range(18)])
    a = adding_one - 1 
    try:
        m1 = long_to_bytes(a)
        if b'moe' in m1:
            b = product // adding_one + 1
            flag = m1 + long_to_bytes(b)
            print(flag)
            break
    except BaseException:   # 忽略所有报错
        pass

大白兔

源码：

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 *

flag = b'moectf{xxxxxxxxxx}'
m = bytes_to_long(flag)

e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697

def encrypt(m , e1 , e2):
    p = getPrime(512)
    q = getPrime(512)
    N = p*q
    c1 = pow((3*p + 7*q),e1,N)
    c2 = pow((2*p + 5*q),e2,N)
    e = 65537
    c = pow(m , e , N)
    return c
    

print(encrypt(m ,e1 , e2))

'''
N = 107840121617107284699019090755767399009554361670188656102287857367092313896799727185137951450003247965287300048132826912467422962758914809476564079425779097585271563973653308788065070590668934509937791637166407147571226702362485442679293305752947015356987589781998813882776841558543311396327103000285832158267
c1 = 15278844009298149463236710060119404122281203585460351155794211733716186259289419248721909282013233358914974167205731639272302971369075321450669419689268407608888816060862821686659088366316321953682936422067632021137937376646898475874811704685412676289281874194427175778134400538795937306359483779509843470045
c2 = 21094604591001258468822028459854756976693597859353651781642590543104398882448014423389799438692388258400734914492082531343013931478752601777032815369293749155925484130072691903725072096643826915317436719353858305966176758359761523170683475946913692317028587403027415142211886317152812178943344234591487108474
c = 21770231043448943684137443679409353766384859347908158264676803189707943062309013723698099073818477179441395009450511276043831958306355425252049047563947202180509717848175083113955255931885159933086221453965914552773593606054520151827862155643433544585058451821992566091775233163599161774796561236063625305050
'''

分析

注意到提供了

c1=(3⋅p+7⋅q)emod  Nc2=(2⋅p+5⋅q)emod  Nc_1 = (3\cdot p + 7\cdot q)^e \mod N \\ c_2 = (2\cdot p + 5\cdot q)^e \mod N \\

对于

c=(a⋅p+b⋅q)emod  Nc = (a\cdot p + b\cdot q) ^ e \mod N

由二项式展开定理

(a⋅p+b⋅q)e=∑i=0e(ei)(a⋅p)i(b⋅q)e−i(a \cdot p + b \cdot q)^e = \sum_{i=0}^{e} \binom{e}{i} (a \cdot p)^{i} (b \cdot q)^{e-i}

对于除了 i=0 和 i=e 的时候， 其他情况：

(a⋅p)x(b⋅q)e−x=ax⋅px⋅be−x⋅qe−x(a \cdot p)^x (b \cdot q)^{e-x} = a^x \cdot p^x \cdot b^{e-x} \cdot q^{e-x} \\

px和qe−xp^x 和 q^{e-x}可以组合出N，那么此时模 N 就等于0

所以只有i=0 和 i=e 的时候，模 N 才会有结果

∴c=(a⋅p)e+(b⋅q)emod  N\therefore c = (a \cdot p)^e + (b \cdot q)^e \mod N

按照以上公式转换 c1, c2

c1=(3p)e1+(7q)e1mod  Nc2=(2p)e2+(5q)e2mod  Nc_1 = (3p)^{e_1} + (7q)^{e_1} \mod N \\ c_2 = (2p)^{e_2} + (5q)^{e_2} \mod N

将c1, c2调整为齐次， 这样可以消去一项

c1e2=(3p)e1⋅e2+(7q)e1⋅e2mod  Nc2e1=(2p)e1⋅e2+(5q)e1⋅e2mod  Nc^{e_2}_{1} = (3p)^{e_1 \cdot e_2} + (7q)^{e_1 \cdot e_2} \mod N \\ c^{e_1}_{2} = (2p)^{e_1 \cdot e_2} + (5q)^{e_1 \cdot e_2} \mod N

用2e1e2c1e2−3e1e2c2e12^{e_1e_2}c_1^{e_2} - 3^{e_1e_2}c_2^{e_1}消去pe1e2p^{e_1e_2}
(注意不是2c1e2−3c2e12c_1^{e_2} - 3c_2^{e_1})

f=(2e1⋅e2c1e2−3e1⋅e2c2e1)mod  N=(14e1⋅e2−15e1⋅e2)⋅qe1⋅e2mod  Nf = (2^{e_1 \cdot e_2} c^{e_2}_{1} - 3^{e_1 \cdot e_2} c^{e_1}_{2}) \mod N = (14^{e_1 \cdot e_2} - 15^{e_1 \cdot e_2}) \cdot q^{e_1 \cdot e_2} \mod N

设 q0=a⋅qxmod  Nq_0 = a \cdot q ^ x \mod N
消掉模N后

q0=a⋅qx−k⋅Nq_0 = a \cdot q ^ x - k \cdot N

∵N=p⋅q\because N = p \cdot q
对 q0q_0 取模p和模q

  1. 模q时

    q0=a⋅qx−k⋅N=q(a⋅qx−1−k⋅p)≡0mod  qq_0 = a \cdot q ^ x - k \cdot N = q(a \cdot q ^ {x-1} - k \cdot p) \equiv 0 \mod q

    ∴q0和N有公因数q\therefore q_0 和 N 有公因数 q
  2. 模p时

    q0=a⋅qx−k⋅N≢0mod  pq_0 = a \cdot q ^ x - k \cdot N \not\equiv 0 \mod p

    ∵N只有因子p,q\because N 只有因子 p , q
    ∴gcd(p0,N)=q\therefore gcd(p_0, N) = q

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *

e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
N = 107840121617107284699019090755767399009554361670188656102287857367092313896799727185137951450003247965287300048132826912467422962758914809476564079425779097585271563973653308788065070590668934509937791637166407147571226702362485442679293305752947015356987589781998813882776841558543311396327103000285832158267
c1 = 15278844009298149463236710060119404122281203585460351155794211733716186259289419248721909282013233358914974167205731639272302971369075321450669419689268407608888816060862821686659088366316321953682936422067632021137937376646898475874811704685412676289281874194427175778134400538795937306359483779509843470045
c2 = 21094604591001258468822028459854756976693597859353651781642590543104398882448014423389799438692388258400734914492082531343013931478752601777032815369293749155925484130072691903725072096643826915317436719353858305966176758359761523170683475946913692317028587403027415142211886317152812178943344234591487108474
c = 21770231043448943684137443679409353766384859347908158264676803189707943062309013723698099073818477179441395009450511276043831958306355425252049047563947202180509717848175083113955255931885159933086221453965914552773593606054520151827862155643433544585058451821992566091775233163599161774796561236063625305050
e = 65537

ee = e1*e2
s1 = pow(c1, e2, N) # 不管啥都把模带上稳妥些
s2 = pow(c2, e1, N)
f = (pow(2, ee, N) * s1 - pow(3, ee, N) * s2) % N
q = GCD(f, N)
p = N // q
assert p*q == N
phi = N - (p+q) + 1
d = inverse(e, phi)
m = pow(c, d, N)
print(long_to_bytes(m))