二次剩余Cipolla
前言
首先二次剩余和cipolla是不同的东西，前者是一个数学定义
对于给定的n和p，在数域Fp内如果存在x满足$x^2 \equiv n (mod p) $，那么n在模p意义下就是二次剩余。
简而言之就是n在模p下能否开根号。
而后者是一个算法，用于快速解出x。
勒让德符号(Legendre symbol)
勒让德符号（在二次剩余下）的定义：
$$
(\frac{a}{p})=
\begin{cases}
1,a为p的二次剩余\
-1,a为p的非二次剩余\
0,a \equiv 0(modp)
\end{cases}
$$
欧拉判别法：$(\frac{a}{p}) \equiv a^{\frac{p-1}{2}}(mod p)$（若a是不被p整除的正整数）
我们可以根据这个判别法来判断a在Fp下是否为二次剩余。
根据费马小定理我们可以作如下推演：（在这里假设条件都是理想条件，比如p是大质数…etc）
$$
a^{p-1} \equiv 1 (modp)
\
(a^{\frac{p-1}{2}}-1) \times (a^{\frac{p-1}{2}}+1) \equiv 0 (mod p)
\
a^{\frac{p-1}{2}} = \pm 1 (modp)
$$
我们可以知道这个勒让德符号的值只可能等于$\pm 1,0$，之所以0会出现是因为我们不确定ap是否互质（或者说a是否是p的倍数），当然这种情况不是我们要讨论的重点。
当$(\frac{a}{p})=1$的时候，设$x^2 \equiv a (modp)$，那么$x^{p-1} \equiv 1 (modp)$就有$a^{\frac{p-1}{2}} \equiv 1 (modp)$，证明完毕。
当$(\frac{a}{p})=-1$的时候，方程$x^2 \equiv a (modp)$无解。因为p是素数，由数论知识可知对于每个$1 \leq i \leq p$，都有唯一的整数j使得$ij \equiv a (modp)$。，所以我们可以把1,2，…p-1分成$\frac{p-1}{2}$对，使得每对的乘积都为a。于是$(p-1)! \equiv a^{\frac{p-1}{2}} (modp)$，且由威尔逊定理可知$(p-1)! \equiv -1(modp)$，因此$a^{\frac{p-1}{2}} \equiv -1(modp)$
于是再加上快速幂的知识，我们就可以快速判定一个数在模p意义下是否是二次剩余的了。
其他前置知识（引理）
- 对于方程$x^2 \equiv n(modp)$，一共有$\frac{p-1}{2}$个不同的n可以使得存在解x。
现在我们来逆向思考一下，从结果出发，如果我们已经知道了u和v都满足$x^2 \equiv n(modp)$的解，那么必然有$p|(u+v)(u-v)$。由于u-v肯定是小于p的数，也就是说不能整除质数p，那么可以说明p肯定整除u+v。这个推断是充要的，也就是说在数域Fp内方程的解是对称且唯二的。另外一共有$\frac{p-1}{2}$种不同的平方，因此存在$\frac{p-1}{2}$个不同的n。
- $(a+b)^p \equiv a^p+b^p (modp)$
显而易见，直接拆开就能证明。
Cipolla算法
我们现在回到主题，希望求出$x^2 \equiv n (mod p) $的一个解。
先随机出一个a使得$(a^2-n)^{\frac{p-1}{2}} \equiv -1 (modp)$。由于p的非二次剩余的数量占一半，所以随机到一个满足条件的a的期望次数是2（或者说很容易随机出来）。显然这个数$(a^2-n)$不能开根号，但是我们强行给这个数开平方根，假设得到的结果是一个复数$\omega$，并且引入类似虚数的“复数域”$F_{p^2}$.那么这个新的数域中的每一个数都可以表示成$a+ \omega b$的形式。其中$\omega$是这个域的虚数单位元。这个“复数域”依然满足封闭性、交换律、结合律以及分配律的，还存在加法零元和乘法逆元（貌似符合环的定义）。
为什么要引入这么一个设定呢？
因为$x \equiv (a+\omega)^{\frac{p+1}{2}}(modq)$
下面证明这个结论：
$$
proof:\omega ^p \equiv - \omega(modp)\
\omega ^p
\equiv \omega \times \omega^{p-1}
\equiv w \times (w^2)^{\frac{p-1}{2}}
\equiv\ w \times (a^2-n)^{\frac{p-1}{2}}
\equiv -\omega
$$
所以
$$
\begin{aligned}
(a+\omega)^{p+1}
&\equiv (a+\omega)^{p}\times (a+\omega)\
&\equiv (a^p+\omega^p)\times (a+\omega)\
&\equiv (a-\omega)\times(a+\omega)\
&\equiv (a^2-\omega^2)\
&\equiv (a^2-(a^2-n))\
&\equiv n(modq)
&\end{aligned}
$$
题目
后来给了hint：
当q mod 4=3时用quadratic residues开方，当q mod 4=1时用cipolla算法开方。
import os
from Crypto.Util.number import *
from secret import flag, hint
m = bytes_to_long(flag + os.urandom(50))
p = getPrime(512)
q = getPrime(500)
n = p * q
h = pow(2, (q - 2022) * (p + 2023), p)
assert h == pow(2, hint, p)
e = 1 << 24_000
c = pow(m, e, n)
print(f'{n = }')
print(f'{c = }')
print(f'{h = }')
print(f'{hint = }')
# n = 22114546923564420607945063747927422619774890007937503484905798897563036431278699718161460968350749338680452479484253816646632515078192048118109272532310403715802657061990320170724360874028667484527150185159662403573637809180151665727445208585725264186578429094937215068881079399747998551453944363665401263
# c = 7274219309267176700435453490636404568410293850833252412471984274955007037941820465929958008672185817002749418809077052781794306899476543760452010370102811167685901654480233874375880047900499814304539829706786470978714629827690730256369200773772396109793338097451559255985268375731804819829315168807228186
# h = 1463929459818798711929811606552273520156490689917243949474579232718301828387871678397965433435537694532920957475947201372279363554005600100100224291888130
# hint = 5610276127312766429915480651516095336201056367031530733662980757514427535721885723009367286870294772595629284861923351543396909892645845139050780691701736
目前的exp就不放了毕竟是错的还特别丑。就当做学了个很神奇的算法吧。（印象中好像有暴力跑的人跑了几个小时，没意思了。
放一个官方的wp但是有个自己写的库的。
好像能跑了，所以放上自己的代码，说起来这是我第一次用GitHub上的代码，也就是这段Cipolla部分，下面的东西是抄wp的，把c关于p的解解出来。
接下来就遇到了第二个函数了。
def quadratic_residues(_p, _c):
return pow(_c, (_p + 1) // 4, _p)这个函数的逻辑是首先知道q%4==3所以(_p + 1) // 4的运算肯定是整除运算。然后用勒让德符号判定这个数c能否开根，如果可以的话那么$1\equiv a^{\frac{p-1}{2}}(mod p)$再用这个乘以a得到$a\equiv a^{\frac{p+1}{2}}(mod p)$而且我们还知道右边的幂是偶数，所以我们直接对幂除以二理论上可以得到$\sqrt(a)$。
当然不嫌麻烦的话理论上cipolla是通杀的，就是慢了点。
然后用中国剩余定理变成关于n的解，并且将这些解存进一个数组里面，然后循环24000次，最后从解里面筛选包含HZNU开头的东西打印出来。
from random import *
from Crypto.Util.number import *
from tqdm import *
class C():
def __init__(self, a ,b ):
self.a = a
self.b = b
def Cmul(a, n, p, i1, i2):
c = a*a -n
t = C ((i1.a * i2.a + i1.b * i2.b % p * c) % p,(i1.b * i2.a + i1.a * i2.b) % p )
return t
def Cqsm(a, n, p, x, y):
z = C(1, 0)
while y :
if y & 1:
z = Cmul (a, n, p, z, x)
x = Cmul (a, n, p, x, x)
y >>= 1
return z
def quick_power(a,b,c):
a=a%c
ans=1
while b!=0:
if b&1:
ans=(ans*a)%c
b>>=1
a=(a*a)%c
return ans
def mod( a, p):
return (a % p + p) % p
def legendre( a, p): # 勒让德符号
return quick_power(mod(a, p), (p - 1) // 2, p)
def Cipolla(n, p):
if n % p == 0:
return 0
if legendre(n, p) != 1 :
return -1
while True:
a=randint(0,p-1)%p
w=(a*a-n+p)%p
if legendre(a * a - n, p) == p - 1 :
break
u = C(a, 1)
u = Cqsm(a, n, p, u, (p+1)//2 )
return mod(u.a, p)
def quadratic_residues(_p, _c):
return pow(_c, (_p + 1) // 4, _p)
n0 = 22114546923564420607945063747927422619774890007937503484905798897563036431278699718161460968350749338680452479484253816646632515078192048118109272532310403715802657061990320170724360874028667484527150185159662403573637809180151665727445208585725264186578429094937215068881079399747998551453944363665401263
c = 7274219309267176700435453490636404568410293850833252412471984274955007037941820465929958008672185817002749418809077052781794306899476543760452010370102811167685901654480233874375880047900499814304539829706786470978714629827690730256369200773772396109793338097451559255985268375731804819829315168807228186
h = 1463929459818798711929811606552273520156490689917243949474579232718301828387871678397965433435537694532920957475947201372279363554005600100100224291888130
hint = 5610276127312766429915480651516095336201056367031530733662980757514427535721885723009367286870294772595629284861923351543396909892645845139050780691701736
p = getPrime(512)
q = getPrime(500)
assert (q - 2022) * 2024 < p - 1
q = hint // 2024 + 2022
assert n0 % q == 0
p = n0 // q
assert p % 4 == 1
assert q % 4 == 3
x = [c]
for _ in tqdm(range(24_000)):
tmp_x, x = x, []
for i in tmp_x:
x1 = Cipolla(i, p)
x2 = p - x1
if x1 == 0 or x2 == 0:
continue
x.append(x1)
x.append(x2)
c = quadratic_residues(q, c)
print(f"{len(x) = }")
for i in x:
for j in [c, q - c]:
m = crt([i, j], [p, q])
if b'HZNUCTF' in long_to_bytes(m):
print(long_to_bytes(m))
exit(0)
事实上最后我也跑不出来……
IITDQ1W%256.png)
这是跑了两个小时的结果捏。
