断网线下+不是自己电脑系列

之

简单密码题

情景再现

某天，有一场比赛，CTF需要做一道简单的密码题，但是环境没有配好，密码方面只有一个python3和pycryptodome库

当时脑子宕机了，没有gmpy2.gcd，我要怎么做题（忘记gcd具体实现了），再加上推不出关系（慌张+没带纸和笔）导致痛失分数，所以开辟这个系列。

依稀还记得题目是

from Crypto.Util.number import *

p, q = [getPrime(512) for _ in range(2)]
e, n = 0x10001, p*q

flag = b"flag{test_flag}"
m = bytes_to_long(flag)

c = pow(m, e, n)
hint = pow((11*p + 83), q, n)

print(f"e = {e} \nn = {n} \nc = {c}\nhint = {hint}".format(e, n,c , hint))

一道数论密码题，我们留到最后来解，先来看一下这种类型的线下前一晚我们要记住的

RSA必要的函数

快速模幂

def mypow(a, b):
    result = 1
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp = exp >> 1
    return result

求最大公因数

def mygcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

拓展欧几里得

def myexgcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        gcd, x1, y1 = myexgcd(b, a%b)
        x = y1
        y = x1 - (a // b) * y1
        return gcd, x, y

求模逆（原理是贝祖定理）

# 如果python --version输出的版本号大于3.8
def myinverse(a,b):
    return pow(a, -1, b)

# python版本小于3.8
def myinverse(u, v):
    # 判断是否互质
    if mygcd(u, v) != 1:
        return "没有逆元"
    return myexgcd(u, v)[1]

数字转字符串

def myl2b(a):
    b = ""
    while a > 0:
        temp = a&0xFF
        b += chr(temp)
        a >>= 8
    return b[::-1]

心中必有的四大数论定理+同余的性质

参考：数论四大定理 | My Blog（好清爽的页面，定理的证明可以详细看这篇）

费马小定理

如果$p$ 是素数且整数a和p的最大公因数是1，那么有$a^{p-1} = 1\mod p$。

如果$p$ 是素数且整数a是p的倍数，那么有$a^{p-1} = 1 \mod p$。

或者总的说，当$p$ 是素数且a是整数，那么有$a^p = a \mod p$。

欧拉定理

前提：一个整数a的欧拉函数$\phi(a)$是指在一个范围[1~a-1]内所有与互质的数的个数。例如$\phi(6)=2$，2到5之间有1和5与6互质

当$\gcd(a,m)=1$

$$ a^{\phi(m)} \equiv 1 \pmod m $$

中国剩余定理，又称为CRT

求解模数可以分解且因数没有平方数的情况（正常的RSA就是其中一种，所以也会衍生出快速解密RSA的方法）

CRT用于求解一下情况

当$n_1$，$n_2$，$n_3$，$n_4$……$n_k$两两互质

$$ \begin{cases} x &\equiv a_1 \pmod {n_1}\\ x &\equiv a_2 \pmod {n_2}\\ x &\equiv a_3 \pmod {n_3}\\ x &\equiv a_4 \pmod {n_4}\\ &…\\ x &\equiv a_k \pmod {n_k}\\ \end{cases} $$

求解过程：

  1. 计算$n = \prod_{i=1}^k n_i $

  2. 对于第$i$个方程：

    ① 计算 $m_i=\frac{n}{n_i}$

    ②计算$m_i$关于$n_i$的逆元$m_i^{-1}$

    ③计算$c_i=m_i \cdot m_i^{-1}$（不需要对$n_i$取模）

  3. 计算方程在模n下的唯一解：$a = \sum_{i=1}^ka_i\cdot c_i \pmod n$

p+1威尔逊定理（实际用的比较少）

当p是一个素数，必定满足下面恒等式

$$ (p-1)!\equiv -1 \pmod p $$

同余的性质

  1. 整除性：$a \equiv b \pmod m \to m|(a-b)$
  2. 传递性：$a\equiv b \pmod m~且~a\equiv c \pmod m\to b\equiv c \pmod m$

  3. 乘法保持性&幂运算保持性：

    $$ a\equiv b\mod m \to \begin{cases} an \equiv bn \pmod m\\ a^n \equiv b^n \pmod m \end{cases} $$

  4. 放大缩小底数：$(km\pm a)^n \equiv (\pm a)^n \pmod m$
  5. 放大缩小模数：$a\equiv b \pmod m \leftrightarrow ka\equiv kb \pmod {km}$
  6. 除法原理：$ka \equiv kb \pmod m \to a\equiv b \pmod {\frac{m}{gcd(k,m)}}$
  7. 降模性：$a \equiv b \pmod m，且d|m\to a\mod b \pmod d$

降模性的推理

  1. 由性质①，得$a-b = km……②$
  2. 又因为$d|m$，所以存在整数$t$，使得$m = td……③$

  1. 将③代入②，得$a-b=k(td)=(kt)d$，说明

    $$ d|(a-b) $$

  2. 按同余定义，这就等价于：

    $$ a\equiv b \pmod d $$

简单例题与EXP

简单数论

1.hint = pow(ap+b, q, n)

就那一开始那道题开篇

from Crypto.Util.number import *

p, q = [getPrime(512) for _ in range(2)]
e, n = 0x10001, p*q

flag = b"flag{test_flag}"
m = bytes_to_long(flag)

c = pow(m, e, n)
hint = pow((11*p + 83), q, n)

print(f"e = {e} \nn = {n} \nc = {c}\nhint = {hint}".format(e, n,c , hint))
'''
e = 65537 
n = 64348263366970828071157857494873264401052708112037784426258800806771893888762184586057068485777444594491807848628902311572186354798973583632221840529059894649943623864268616150505783604783797075046208076234016963024906184463844053891383660752794304602854869104710968492267390573146230984335750134128192516687 
c = 58657393682302351805025492006450112485075931812685317074534840294705759588274627949054545807955872582172943604286628173924666443560199473275321958035428425140143073400041596285301377279395416088044556526433727520227677221092590248526736648512727991470389806082564592214466546324488189843676489622199254870828
hint = 16497484182653912230570503764276143592365988557632188414659894083347901207850734670312726995601246764961615075085580535471871121981773660223672498028279643695141558449507569629842220752756701591051340403307726608532125377898112278818860593465377784022622401057822937415574264242491437578199027316632072141328
'''

我们有hint

$$ \begin{array}{l} 由题意知：\\ &hint \equiv (ap+b)^q \pmod n\\ 由降模性，有\\ &hint \equiv (ap+b)^q \pmod p\\ 由放大缩小底数，有\\ &hint \equiv b^q \pmod p\\ 由幂运算保持性，两边同时幂上p\\ &hint^{p} \equiv b^{p\cdot q} \pmod p\\ 由费马小定理，有\\ &hint \equiv b^{p\cdot q} \pmod p\\ 即\\ &hint = b^n + kp \to kp = b^n - hint \end{array} $$

证毕

EXP

from Crypto.Util.number import *


e = 
n = 
c = 
hint = 

def mygcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
# 为了快速计算幂，计算83^n模上n
p = mygcd(pow(83,n,n)-hint, n)

q = n//p
phi = (p-1)*(q-1)

d = inverse(e, phi)

print(long_to_bytes(pow(c, d, n)).decode())

先写到这里，后面补

最后修改：2025 年 12 月 22 日
© 允许规范转载
很强的定力