1.twoEs1

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
28
29
30
31
32
from Cryptodome.Util.number import *
import random

flag=b"SPCCTF{********}"

p, q = getPrime(512), getPrime(512)
n = p * q

e1 = random.getrandbits(32)
e2 = random.getrandbits(32)

import gmpy2
s,s1,s2=gmpy2.gcdext(e1,e2)
print(s)

m = bytes_to_long(flag)
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

print(f'{n = }')
print(f'{e1 = }')
print(f'{e2 = }')
print(f'{c1 = }')
print(f'{c2 = }')

'''
n = 77653027019410283582708662091841984922043011758121679079881183020813164663803315218162399044305258074482737579924642303624296916990420038267507847806411365847770079739424288020008734096352715536212355610499244337263033620679172659903396470522388964976403280440005666750783772493205491694203801534799771603973
e1 = 1550550838
e2 = 4196113069
c1 = 10879882027555312937608696756143487708492509877667613620249639748606727334006539946052668627697088875994270713711095280209616987454727654075073679556671706894288288425066016765935927179268631914629763649753266424293357163466575462028472324055698901991171526421270840161635556574472647431065514324250656887711
c2 = 3011958986718808526365150648555525977083765700624932707761381505508399298854491454270664897732491521128964864382168158216240628717617068568110917894811504799962807736416471284350198523924590448858301736435406723758509936349838419125901147351088181623044341056413457153562300106346324761118425649126782967195
'''

题目给了提示：使用扩展欧几里得算法

回一下扩展欧几里得算法的内容：

对于整数a，b，方程$ ax+by=c $有整数解组$ (x,y) $

且根据裴蜀定理，方程有整数解当且仅当c是a，b最大公约数的倍数，即$ c\mid gcd(a,b) $

所以这道题的思路就是根据方程组$ \begin{cases}c1=m^{e1}\mod n\c2=m^{e2}\mod n\end{cases} $解出m

再把长整数m转化成字符串flag

题目中也给出了提示

1
2
3
import gmpy2
s,s1,s2=gmpy2.gcdext(e1,e2)
print(s)

该代码等价于求$ e1s1+e2s2=gcd(e1,e2)=s $的整数解组$ (s1,s2) $

并验证s的值，如果s为1

就有$ m=m^{e1s1+e2s2}\mod n=c1^{s1}\times c2^{s2}\mod n $

我们就可以通过s1,s2来求出m，继而得到flag

要注意的一点是，s1，s2的结果可能是负数，就有

$ c^s=c^{\frac{1}{\lvert s\rvert}}=(c^{-1})^{\lvert s\rvert} $

所以就需要先求出底数的逆元$ c^{-1} $

先尝试输出一下s，s1，s2，看下结果

发现果然e1，e2是互素的，那么上面结论就可适用了，但是s2是负数，我们需要求c2的逆元

由于$ c2c2^{-1}\mod n=1 $

两边同乘$ c2^{-1} $就有$ c2^{-1}=c2^{-1}\mod n $

这样我们就可以构建解题算法了

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 long_to_bytes
import random

n = 77653027019410283582708662091841984922043011758121679079881183020813164663803315218162399044305258074482737579924642303624296916990420038267507847806411365847770079739424288020008734096352715536212355610499244337263033620679172659903396470522388964976403280440005666750783772493205491694203801534799771603973
e1 = 1550550838
e2 = 4196113069
c1 = 10879882027555312937608696756143487708492509877667613620249639748606727334006539946052668627697088875994270713711095280209616987454727654075073679556671706894288288425066016765935927179268631914629763649753266424293357163466575462028472324055698901991171526421270840161635556574472647431065514324250656887711
c2 = 3011958986718808526365150648555525977083765700624932707761381505508399298854491454270664897732491521128964864382168158216240628717617068568110917894811504799962807736416471284350198523924590448858301736435406723758509936349838419125901147351088181623044341056413457153562300106346324761118425649126782967195

import gmpy2
s,s1,s2=gmpy2.gcdext(e1,e2)
print(s)
print(s1)
print(s2)
if s2 < 0:
    c2_inv = pow(c2, -1, n)
    m = (pow(c1, s1, n) * pow(c2_inv, abs(s2), n)) % n
else:
    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
flag=long_to_bytes(m)
print(flag)

运行得到输出结果

SPCCTF{it_is_ez_70_4774ck!}

twoEs1.py

2.twoEs2

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
28
from Cryptodome.Util.number import *
import random

flag=b"SPCCTF{********}"

p, q = getPrime(512), getPrime(512)
n = p * q

e1 = random.getrandbits(32)
e2 = random.getrandbits(32)

m = bytes_to_long(flag)
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

print(f'{n = }')
print(f'{e1 = }')
print(f'{e2 = }')
print(f'{c1 = }')
print(f'{c2 = }')

'''
n = 97600241525101615748091592571664660926639880623676630098513390980179339048294452878617774530804846547759693682625720452045482941031433063601264167464483345140203593650062234011147495096867025786848883396312986373098722431552517575960894385653813275110519118159478403718867113163144951756435064109978693850991
e1 = 3739335288
e2 = 3124897683
c1 = 33002001040793361121205743705051566694083960204437803400110996553874970546459769940895274538944142911035661180721041433582055055901827086366079458238180515982882281159369335115689197909674012289803866694817803339799332165760217770985620911446230237865457225365735286754884597360255964535103536362788889343153
c2 = 28612632923221914052449458260170537094022260373135401108346955487860713981145320349945832078855063911329616383875004373295934310132767249858424266864981319085969453037587482565982836138763906635775429377847559657878241052164215585546465219419202751784070881845017799754069244601020027997406547478196338470880
'''

尝试直接照搬上题的思路

验证下s，s1，s2的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import long_to_bytes
n = 97600241525101615748091592571664660926639880623676630098513390980179339048294452878617774530804846547759693682625720452045482941031433063601264167464483345140203593650062234011147495096867025786848883396312986373098722431552517575960894385653813275110519118159478403718867113163144951756435064109978693850991
e1 = 3739335288
e2 = 3124897683
c1 = 33002001040793361121205743705051566694083960204437803400110996553874970546459769940895274538944142911035661180721041433582055055901827086366079458238180515982882281159369335115689197909674012289803866694817803339799332165760217770985620911446230237865457225365735286754884597360255964535103536362788889343153
c2 = 28612632923221914052449458260170537094022260373135401108346955487860713981145320349945832078855063911329616383875004373295934310132767249858424266864981319085969453037587482565982836138763906635775429377847559657878241052164215585546465219419202751784070881845017799754069244601020027997406547478196338470880
import gmpy2
s,s1,s2=gmpy2.gcdext(e1,e2)
print(s)
print(s1)
print(s2)
c2_inv = pow(c2, -1, n)
m,is_exact = gmpy2.iroot((pow(c1, s1, n) * pow(c2_inv, abs(s2), n)) % n,s)
flag=long_to_bytes(m)
print(flag)

得到输出结果

SPCCTF{3z_C0mm0n_M0du1u5_4774ck}

要注意的是，对结果开方一定要用gmpy2中的iroot函数，不要用pow（x，1/3）或者x^{1/3}，分数会转化成浮点数导致直接随时计算精度并且会报错

并且iroot函数输出的是一个元组（tuple），第一个输出的是结果，第二个输出的是布尔值。不要直接用m去赋值，会报错

twoEs2.py

3.Basic Number theory

题目提示试着了解一下费马小定理、同余运算的规则

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

flag=b'SPCCTF{********}'

def gift(m, prime):
    return pow(m, (prime + 1) // 2, prime)

m = bytes_to_long(flag)
p = getPrime(256)
q = getPrime(256)

print(f'p = {p}')
print(f'q = {q}')
print(f'gift1 = {gift(m, p)}')
print(f'gift2 = {gift(m, q)}')

'''
p = 105567001902149483225233801278030547652749833525571608392930512645364400245999
q = 81511997683966846473333390828680375856568631631277717336250575831122994340471
gift1 = 105419799642658114984760815640014033297217363704585842609128111376906603236722
gift2 = 81364795424475478232860405190663861501036161810291951552448174562665197331194
'''

因为$ gift\equiv m^{\frac{p+1}{2}}(\mod p) $

两边平方可得：

$ gift^2\equiv m^{p+1}(\mod p)=m^p*m(\mod p) $

由费马小定理$ m^p\equiv m(\mod p) $，所以

$ gift^2\equiv m*m(\mod p)=m^2(\mod p) $

这意味着gift是$ m^2 $的平方根，所以$ gift\equiv \pm m(\mod p) $

由于这题的特殊性，构造的m本身就是二次剩余，无需再过多证明

所以可能的m满足：

$ m\equiv \pm gift1\mod p $

$ m\equiv \pm gift2\mod q $

这个格式已经很明显了，接下来只需要利用中国剩余定理（CRT）解出m即可得到flag

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from Cryptodome.Util.number import long_to_bytes, GCD
from itertools import product

# 题目给出的数据
p = 105567001902149483225233801278030547652749833525571608392930512645364400245999
q = 81511997683966846473333390828680375856568631631277717336250575831122994340471
gift1 = 105419799642658114984760815640014033297217363704585842609128111376906603236722
gift2 = 81364795424475478232860405190663861501036161810291951552448174562665197331194

def solve_crt(remainders, moduli):
    """简单的中国剩余定理实现"""
    M = 1
    for m in moduli:
        M *= m
    
    result = 0
    for r, m in zip(remainders, moduli):
        Mi = M // m
        # 求 Mi 模 m 的逆元
        # 因为 m 是素数且 Mi 不含 m 因子，逆元一定存在
        inv = pow(Mi, -1, m)
        result += r * Mi * inv
    
    return result % M

# 可能的余数组合
# m % p 可能是 gift1 或 -gift1 (即 p - gift1)
# m % q 可能是 gift2 或 -gift2 (即 q - gift2)
candidates_p = [gift1, (p - gift1) % p]
candidates_q = [gift2, (q - gift2) % q]

print("开始尝试还原 m...")

for cp in candidates_p:
    for cq in candidates_q:
        # 使用 CRT 合并
        m = solve_crt([cp, cq], [p, q])
        
        # 尝试转换为字节
        try:
            flag_bytes = long_to_bytes(m)
            if b'SPCCTF{' in flag_bytes:
                print(f"找到 Flag: {flag_bytes.decode()}")
                break
        except:
            continue
    else:
        continue
    break
else:
    print("未找到符合格式的 Flag，可能需要检查逻辑。")

# 额外检查：如果 m 比 p*q 小很多，直接输出看看
# 有时候 m 直接等于 gift1 (如果 m < p 且 m 是二次剩余)
# 我们上面的逻辑已经覆盖了 m = gift1 的情况 (当 cp=gift1, cq=gift2 时)

运行得到输出结果

SPCCTF{Do_U_like_the5e_2_gif7?}

再对上面的代码进行一些补充：

1
2
3
4
5
6
7
8
9
10
# 可能的余数组合
# m % p 可能是 gift1 或 -gift1 (即 p - gift1)
# m % q 可能是 gift2 或 -gift2 (即 q - gift2)
candidates_p = [gift1, (p - gift1) % p]
candidates_q = [gift2, (q - gift2) % q]

print("开始尝试还原 m...")

for cp in candidates_p:
    for cq in candidates_q:

为什么还要进行这两步的循环？

因为CRT中的两个方程式不确定的，两组方程各有两种可能性，合起来就有四种可能，这四种可能中数学上都是合法的可能解，但是对于密码学来说，四个里面只有一个解会输出正确flag格式的答案，剩余三个会输出乱码，所以为了唯一确定答案，必须尝试每一种可能

其次，candidate_p中为什么要用(p - gift1) % p而不是直接用-gift1？

对于python来说，后者确实可以，这涉及到python语言的模运算算法，无论你输入的数是正是负，python返回的一定是正数，但是对于C或者C++，就会直接返回负数，这是一种防御性写法，可以使得这行代码可以在任意语言中运行，只需要修改对应的语法

1
2
except:
            continue

这行代码的作用是什么？

此代码上方尝试对解出的m做转化成字符串的操作，这行代码可以保证即使尝试出错，也只是跳过当前循环，继续下一次循环，而不是因为出错而直接终止程序，这也是一种防御性写法

想具体了解费马小定理的形式和证明可以看下面这篇文章

https://www.yuque.com/fragrantveget/ucxpnh/wkc4703mgk7z2g9t?singleDoc# 《费马小定理（Fermat’s Little Theorem）》

有关同余运算可以看下面这篇文章

https://www.yuque.com/fragrantveget/ucxpnh/qvoa3zrzhc5ovi5u?singleDoc# 《模运算的基本性质》

Basic Number theory(1).py

4.家人们！谁懂啊，RSA签到都不会 (初级)

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

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
e = 65537
n = p*q
c = pow(m,e,n)
print(f'p = {p}')
print(f'q = {q}')
print(f'c = {c}')
'''
p = 12567387145159119014524309071236701639759988903138784984758783651292440613056150667165602473478042486784826835732833001151645545259394365039352263846276073
q = 12716692565364681652614824033831497167911028027478195947187437474380470205859949692107216740030921664273595734808349540612759651241456765149114895216695451
c = 108691165922055382844520116328228845767222921196922506468663428855093343772017986225285637996980678749662049989519029385165514816621011058462841314243727826941569954125384522233795629521155389745713798246071907492365062512521474965012924607857440577856404307124237116387085337087671914959900909379028727767057
'''

这是一道典型的RSA算法题，主要就是考察RSA的加解密过程，以及公钥和私钥的关系

RSA的加密过程为$ c\equiv p^e(\mod n) $

解密过程为$ p\equiv c^d(\mod n) $

p,q是随机生成的两个大素数

$ z=(p-1)*(q-1) $

公钥和私钥的关系是

$ e*d\equiv 1(\mod z) $

知道了以上过程，解这道题就很简单了

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import long_to_bytes
e = 65537
p = 12567387145159119014524309071236701639759988903138784984758783651292440613056150667165602473478042486784826835732833001151645545259394365039352263846276073
q = 12716692565364681652614824033831497167911028027478195947187437474380470205859949692107216740030921664273595734808349540612759651241456765149114895216695451
c = 108691165922055382844520116328228845767222921196922506468663428855093343772017986225285637996980678749662049989519029385165514816621011058462841314243727826941569954125384522233795629521155389745713798246071907492365062512521474965012924607857440577856404307124237116387085337087671914959900909379028727767057
z = (p-1)*(q-1)
n = p*q
d = pow(e,-1,z)
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)

运行得到输出结果

LitCTF{it_is_easy_to_solve_question_when_you_know_p_and_q}家人们！谁懂啊，RSA签到都不会 (初级)(1).py

5.basics

binary.txt

打开一看里面全是二进制数

使用cyberchef网页将其转化，文本里面是按8为一分，现试试看utf-8

转化成了有意义的文字，将其复制出来

可以发现里面的一段文字是经过另一种特殊的编码得到的，并且提示只有大小写字母还有0-9，有时会出现/和+

直接把这个特征拿去问ai就好了

可以得知这段文本经过base64编码

同样的，单独把明文复制出来

提示说这些字母通过一些常数转换，且跟罗马人相关，第一时间想到可能是凯撒密码

确实得到了有意义的文字

还是将明文单独复制出来

最后发现这是一个代换密码分析，代换密码的密钥空间有26！个，肯定不能通过枚举字母表来爆破，所以我们可以通过英文的统计特性来分析这段密文

具体的代换密码分析知识详见

https://www.yuque.com/fragrantveget/ucxpnh/dd0g6gwbhz4votk9?singleDoc# 《基于《密码学原理》对于密码学的学习》1.3.1 单表代换的密码分析

里面非常重要的一个分析提示是flag格式为utflag{…} ，无论如何代换，密文中总会保留这一组字母，在密文中可以找到vtsoid{x0l_ty4tk_ly4t_j_h4oo_hngbt0}，因此vtsoid就对应utflag

现在我们就可以知道

v-u

t-t

s-f

o-l

i-a

d-g

接下来统计密文中字母出现频数，推测高频出现的几个字母

写一个脚本来自动统计字母频数

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import re
from collections import Counter

def count_letters():
    # 1. 获取用户输入
    raw_input = input("请输入一段任意英文文本（可包含符号、数字、小写字母）：\n> ").strip()

    # 2. 数据清洗核心步骤
    # 使用正则表达式 [^A-Za-z] 匹配所有非字母字符，并将其替换为空字符串
    # 然后统一转换为大写，确保统计标准一致
    clean_text = re.sub(r'[^A-Za-z]', '', raw_input).upper()

    # 3. 验证清洗后的结果
    if not clean_text:
        print("\n⚠️  输入无效！未检测到任何英文字母（可能全为符号、数字或空字符串）。")
        return

    # 4. 统计每个字母的出现次数
    count = Counter(clean_text)

    # 5. 确保 A-Z 都在字典中（未出现的设为 0，保持表格完整性）
    for letter in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
        count.setdefault(letter, 0)

    # 6. 打印完整字母频次表
    print("\n" + "=" * 30)
    print("【完整字母频次统计表】")
    print("=" * 30)
    print(f"{'字母':<8} {'出现次数'}")
    print("-" * 30)
    for letter in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
        # 只有当次数大于0时才显示具体数字，或者你可以选择始终显示0
        # 这里为了清晰，始终显示数字
        print(f"{letter:<8} {count[letter]}")
    
    # 7. 获取频数前9的字母
    # most_common(n) 会自动处理排序：先按频数降序，若频数相同则按首次出现顺序
    # 如果需要频数相同时按字母表顺序(A-Z)排列，需要自定义排序逻辑（见下方注释）
    
    # 【进阶排序】：如果希望频数相同的情况下，按字母表 A-Z 顺序排列
    # 将字典项转换为列表并排序：主要关键字是频数(降序)，次要关键字是字母(升序)
    sorted_items = sorted(count.items(), key=lambda x: (-x[1], x[0]))
    top9 = sorted_items[:9]

    # 8. 打印前9高频字母
    print("\n" + "=" * 30)
    print("【频数前 9 的字母（高频到低频）】")
    print("=" * 30)
    print(f"{'排名':<6} {'字母':<8} {'频数'}")
    print("-" * 30)
    
    if not top9:
        print("无数据可显示。")
    else:
        for i, (letter, freq) in enumerate(top9, start=1):
            # 如果频数为0，说明后面都是0，可以选择停止打印或继续打印
            if freq == 0:
                break
            print(f"{i:<6} {letter:<8} {freq}")

if __name__ == "__main__":
    count_letters()

输入密文，得到统计结果

出现频数最高的9个字母是E,T,A,O,I,N,S,H,R

hwxdnitvoitjwxk! gwv yiqa sjxjkyau tya padjxxan hngbtwdnibyg hyiooaxda. yana jk i soid swn ioo gwvn yinu asswntk: vtsoid{x0l_ty4tk_ly4t_j_h4oo_hngbt0}. gwv ljoo sjxu tyit i owt ws hngbtwdnibyg jk fvkt pvjoujxd wss tyjk kwnt ws pikjh rxwloauda, ixu jt naioog jk xwt kw piu istan ioo. ywba gwv axfwgau tya hyiooaxda!

hwxdnitvoitjwxk! 长难句起手，猜测这个单词是congratulations

vtsoid{x0l_ty4tk_ly4t_j_h4oo_hngbt0}

出现频数最高的9个字母是E,T,A,O,I,N,S,H,R

根据上面的猜测，我们就可得到：

t-t

i-a

o-l

w-o

j-i

n-r

x-n

d-g

s-f

v-u

k-s

现在出现频数最高的前9个字母还剩e和h，对应的剩余还有a和y，由于a出现频数高于y

所以

a-e

y-h

现在就可以把已知的字母将密文代换，得到结果

congratulations! ou ha_e finishe the eginner cr_to_ra_h challenge. here is a flag for all our har efforts: utflag{n0l_th4ts_ly4t_i_h4oo_cr_to0}. you wi__ fi_d that a lot of cr_to_ra_h_ is just pu__li_g off this sort of hasi_ kno_le_ge, and it really is not so hard after all. hope you en_oyed the challenge!

高频字母推出后，剩下的字母通过单词判断即可推出

congratulations! you have finished the beginner cryptography challenge. here is a flag for all your hard efforts: utflag{n0w_th4ts_wh4t_i_c4ll_crypt0}. you will find that a lot of cryptography is just building off this sort of basic knowledge, and it really is not so hard after all. hope you enjoyed the challenge!

可以得到flag

utflag{n0w_th4ts_wh4t_i_c4ll_crypt0}

ciphertext.txt

字母频数统计.py

可以说，没有这个flag头和congratulations提示，这个代换分析会变得异常困难，没想到啃书啃得内容真的能排上用场，靠自己慢慢推出来还是挺有意思的

原文链接：https://www.yuque.com/fragrantveget/ucxpnh/qngkemgfrl76by3t?singleDoc# 《SPC:CTF 练练手》