CRT中国剩余定理复现

极客大挑战2024中国剩余定理复现

CRT(中国剩余定理)

一些定理的证明

1.证明辗转相除法

a=bq+r

证明gcd(a,b)=gcd(b,r)

已知gcd(a,b)|a,gcd(a,b)|b

r=a-bq,—>gcd(a,b)|r

所有gcd(a,b)<=gcd(b,r)

gcd(b,r)|b,gcd(b,r)|r并且gcd(b,r)|a

所以gcd(b,c)<=gcd(a,b)

代码实现

def gcd(a,b):
    while b!=0:
        r=a%b
        a=b
        b=r
    return a
print("请输入a")
a=int(input())
print("请输入b")
b=int(input())
print(gcd(a,b))
n=2
while n!=0:
    n=n-1
    print(n)

证明裴蜀定理

如果a和b是不为0的整数，则有整数x,y，是的ax+by=gcd(a,b)

gcd(a,b)=gcd(b,a%b=r1)=gcd(r1,b%r1=r2)=gcd(r2,r1%r2=r3)=gcd(r3,r2%r3=0),,r3为最大公约数

r3=r1-?r2,=r1-(b-?r1)=?r1+?b=?(a-b?)+?b=?a+?b(?为任意整数)

推论：

a,b互质<–>ax+by=1(a,b不全为0)

如果a和b是不全为0的整数，并且ax+by=c有解，那么c一定是gcd(a,b)的整数倍

a和b两项的裴蜀定理可以推广到多项（ax+by+cz=gcd(a,b,c)

扩展欧几里得算法

1.用于处理一元线性同余方程组问题

举例一个类似的线性矩阵，满足m之间互质，则对于任意a，X有解。

Mi表示m₁*m₂*…*m_n-1

$$\prod_{i=1}^{n} i=M$$

t_i=M_i^-1即他们互为倒数

可以得到t_i*m_i=1mod(m_i)

可以得到

$x=a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+\cdots +a_{n}t_{n}M_{n}+kM=kM+\sum _{i=1}^{n}a_{i}t_{i}M_{i},\quad k\in \mathbb {Z} .$

如果对x去模M则就有 $x=\sum _{i=1}^{n}a_{i}t_{i}M_{i}.$ 唯一解，也是最小解

做题WP

from Crypto.Util.number import *
from secret import flag

p = [getPrime(1024) for i in range(4)]
A = random_matrix(ZZ,4,4)
x = vector(p)
C = A*x
m = bytes_to_long(flag)
C_list = [m^2 % p[i] for i in p]

print(A.list())
print(C.list())
print(C_list)

p = [getPrime(1024) for i in range(4)]随机生成四个1024位的大素数。

A = random_matrix(ZZ,4,4)随机生成一个4*4矩阵。

x = vector(p)将p变成4维向量X。

C=A*X//A与X矩阵相乘得到C。

m = bytes_to_long(flag)。将flag从字节转换成一个长整数。

C_list = [m^2 % p[i] for i in p]。将m²模p中的每个数，得到有四个元素的列表C_list。

我们反推这个题，已知C，A，C_list。先通过C = A*x反推出X然后得到P。然后通过P利用中国剩余定理，得到m²最后得到flag

python解密代码如下

from sympy import Matrix, floor, sqrt
from sympy.ntheory.modular import solve_congruence
from Crypto.Util.number import long_to_bytes

# 已知矩阵 A 和向量 C
A = Matrix([[0, 3, 13, -14], [3, 23, 0, -2], [1, 0, -2, -2], [0, 6, 23, -1]])
C = Matrix([
    240291916026450853326299190970230346016172195881040521282143062887044415649037529786726996601318182310764736460576505905853588791461834136499382728467644441025444276310127878088660033443492552638740545000926442503220444210798223930409598242340803157100462304319147723884276724762657521839584789559871925165760,
    2717720293948071692375399406613869670771599238582123998465247515177734926976499453293454850275431149956050441808723146824893873695181057831740557746748569414755121567964485941329619805530387035869417797456365550166284561344481782536841750836701781173446215190576686468572143336023976555984489188188587442599216,
    -533548100977056273203151152482369923618163132589214562561487066657940175907095576692149455190734101432827064737665463493053792538736227178020400115918642405290979502807029452417998359787492016936318980930297669652709045919397558996256596914383243332942443302758025216611814306941895320000161610678184972875739,
    4222318758561393352580663599337085248915805543151591039306576069590530359211724446951051459283547556643285440266930522614603788902068741368143298763016144907986405290404635699093289327803758616517987063925407686664235188616756483626348375811993157044295992929396465160478520815655459249252288507190574794338922
])

# 求解 x 向量
x = A.LUsolve(C)  # 使用 sympy 的 LU 分解来解线性方程组，避免浮点数溢出

# 模数和余数列表
p = list(x)
C_list = [
    1480960470329638043680688727038239738930475793098218659683171073192289938334049452419257815941575064684613256921077170955193683633002228493232830695650419041071577617101320586384
] * 4

# 使用 solve_congruence 求解 m^2
congruences = [(C_list[i], p[i]) for i in range(4)]
m_squared, _ = solve_congruence(*congruences)

# 求解 m
m = floor(sqrt(m_squared))
flag = long_to_bytes(m)

print("解出的 flag:", flag)

flag: b’MaybeLinearAlgebraStillNeedYourEffort’

扩展知识–如果模数不互质

扩展欧几里得定理和裴蜀定理。

描述：一定存在整数 x, y 满足等式 a * x + b * y = gcd(a,b)

证明，。

如果b=0,，则 gcd⁡(a,b)=∣a∣,此时我们取x=1或-1和y=0显然满足ax+by=d。

如果b≠0,根据欧几里得几何算法，可以写出：

a=b*q+r即a其中 q 是商，r是余数，且 0≤r<∣b∣。根据这一表示法，我们有gcd(a,b)=gcd(b,r)

现在我将问题转化为证明：存在整数x’和y’，是的

bx’+ry’=gcd(b,r)

根据数学归纳法，这个等式成立。

由于r=a-bq,我们可以将r带入上式

*bx’+(a-bq)y’=d,

ay’+b(x’-qy’)=d

这表明，若令x=y’和y=x’-qy’，那么ax+by=d

那么我们一步步递归就能得到余数，有点类似辗转相除，递归的每一步b,q,d,,a都是整数，递归到最后一步的整除倍数

r_k-2=r_k-1*q_k+r_k

r_k-1=r_k*q_k+1+0

r_k=r_k-2-q_kr_k-1

d=x_kr_k-2+y_kr_k-1

明显x_k=1,y_k=-q_k为整数

向上步步递归可以得到的x和y也为整数。

我们通过扩展欧几里得算法一般得到的是特解(x₀,y₀)满足

ax+by=d.我们需要证明所有满足此方程的整数解（x,y)的形式是。k为任意整数。

x=x₀+(b/d)k,

y=y₀-(a/d)k;

我们将两对解相减得到

a*(x₁-x₀)+b(y₁-y₀)=0*

a*(x₁-x₀)=-b*(y₁-y₀)

满足比例关系-b/a=(x₁-x₀)/(y₁-y₀)

并且gcd(a,b)=d，对a和b同时除以公因子,b/a完成化简。

就能得到*x₁-x₀=(b/d)k||y₁-y₀=-(a/d)*k

最后得到通解。

中国剩余不互质的应用（假设求的数为ans)

中国剩余定理是用于求一个最小的xx，满足$x≡ci(modmi)cocrt$

一般的中国剩余定理都满足mi之间互质，这里扩展的是不互质的情况

假设我们现在有两条方程:

$$
\left{
\begin{aligned}
x & ≡ c_1(modm_1) \
x &≡ c_2(mod m_2)\
\end{aligned}
\right.
$$

展开同余
$$
\left{
\begin{aligned}
x=c_1+m_1k_1 \
x=c_2+m_2k_2\
\end{aligned}
\right.
$$

联立得解:$m_1k_1=(c_2-c_1)+m_2k_2$

若方程有解,$(m1,m2)|(c2−c1)$

令$d=(m1,m2)$

两边同时除以d

$m_1 k_1\over d$=$c_2-c_1\over d$(mod $m_2 \over d$)

k1=inv($m_1 \over d$,$m_2 \over d$)*$c_2-c_1\over d$(mod $m_2 \over d$)

最后得到：$x≡inv(m1/d,m2/d)×(c2−c1)/d×m1+c1(mod(m1m2)/d)$

from Crypto.Util.number import *
import random

flag = b'SYC{...}'
m = bytes_to_long(flag+b'\x01'*23)

p = [0]*5
c = [0]*5
for i in range(5):
    p0 = random.randint(2**100,2**101)
    p[i] = p0
c = [m%p[i] for i in range(5)]
print(f"p = {p}")
print(f"c = {c}")

"""
p = [1921232050179818686537976490035, 2050175089402111328155892746480, 1960810970476421389691930930824, 1797713136323968089432024221276, 2326915607951286191807212748022]
c = [1259284928311091851012441581576, 1501691203352712190922548476321, 1660842626322200346728249202857, 657314037433265072289232145909, 2056630082529583499248887436721]
"""

m模p得到c，并且p不是互质的。这里要使用不互质的算法

解题代码

from gmpy2 import *
from functools import *
from Crypto.Util.number import *
from sympy import gcdex


def uni(P,Q):
    c1,m1=P
    c2,m2=Q
    d=gcd(m1,m2)
    assert (c2-c1)%d==0
    l=inverse(m1//d,m2//d)
    print(l)
    return (c1 + (c2 - c1) // d * l * m1) % lcm(m1, m2), lcm(m1, m2)#返回的是一个元组


def CRT(eq):
    return reduce(uni, eq)#


ms = [1921232050179818686537976490035, 2050175089402111328155892746480, 1960810970476421389691930930824,
      1797713136323968089432024221276, 2326915607951286191807212748022]
cs = [1259284928311091851012441581576, 1501691203352712190922548476321, 1660842626322200346728249202857,
      657314037433265072289232145909, 2056630082529583499248887436721]
flag, lcm = CRT(zip(cs, ms))#把两个列表打包，依次对应有点像二维数组,但其实返回的是元组
print(long_to_bytes(flag))
'''
90728466640069861245808807287
88626484234357944548738818769
341093009098982253215042305269
635742831101395206473512021361
b'SYC{wha+s_wr0n9!_CRT_bu+_n0+_<0mpr1me!}\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01'
'''

rnocrt

import hashlib
from Crypto.Util.number import *
from secret import x

m = [getRandomNBitInteger(256) for i in range(10)]
u = hashlib.sha256(x).hexdigest()
assert u[:5]==b'6a651'
flag = b'SYC{'+u+b'}'
c = [x % i  for i in m]
print(m)
print(c)

#[207867980504656835313307696396607264603, 245036212212570610987366430554968489325, 270836744824069537438646110613439698666, 319275775495422875474878625752594133023, 254268823435329877199449670714528712873, 213093607196415232366564484229844568444, 246921085368773491003187313772615702950]
#[150031581047390726903711035932621949276, 21260202376534810598778595491323328519, 144049733622518360270048059408969512643, 236920143187836025924037873968303507493, 99781504248790469459151935530031893836, 69236016568483424294966410179787943383, 20613188366058016717435734248097940419]

这个题跟上个题很像，但是上一个返回的最小值就是flag这个需要一定的爆破，并且注意数据的类型

因为f是被mod各个mi最大公约数的结果，属于值最小的可能,我们可以挨个f+i/*lcm知道得到最大值

from Crypto.Util.number import inverse
from gmpy2 import *
from functools import *
import hashlib
def uni(P,Q):
    c1,m1=P
    c2,m2=Q
    d=gcd(m1,m2)
    assert (c2-c1)%d==0
    l=inverse(m1//d,m2//d)
    print(l)
    return (c1 + (c2 - c1) // d * l * m1) % lcm(m1, m2), lcm(m1, m2)#返回的是一个元组


def CRT(eq):
    return reduce(uni, eq)#


ms = [207867980504656835313307696396607264603, 245036212212570610987366430554968489325, 270836744824069537438646110613439698666, 319275775495422875474878625752594133023, 254268823435329877199449670714528712873, 213093607196415232366564484229844568444, 246921085368773491003187313772615702950]
cs = [150031581047390726903711035932621949276, 21260202376534810598778595491323328519, 144049733622518360270048059408969512643, 236920143187836025924037873968303507493, 99781504248790469459151935530031893836, 69236016568483424294966410179787943383, 20613188366058016717435734248097940419]
f, lcm = CRT(zip(cs, ms))#把两个列表打包，依次对应有点像二维数组,但其实返回的是元组
for i in range(1000000):
    x=str(f+i*lcm).encode()
    u=hashlib.sha256(x).hexdigest()
    flag="SYC{"+u+"}"
    if u[:5]=="6a651":
        print(flag)
        break
'''
SYC{6a651b7ce47b35cc1aca565028fb633fab9e35ca08e45d5ce987a6caeb500465}
'''

crypto

#crypto

CRT中国剩余定理复现

http://example.com/2024/12/29/极客大挑战2024中国剩余定理复现/

Beitragsautor

fox

Veröffentlicht am

December 29, 2024

Urheberrechtshinweis

RSA维纳攻击及其扩展 Vorheriger

AES加密以及代码实现 Nächster