二次剩余

定义

对与$p$剩余系中的$a$,若存在$x$满足

$x^2 \equiv a \pmod{p}$

则称$a$是模$p$的二次剩余,否则就称$a$是模$p$的非二次剩余。

性质1

在模$p$的完系中，总共有$\frac{p-1}{2}$个二次剩余，$\frac{p-1}{2}$个非二次剩余，并且二次剩余对应的$x$有$x \in \{1,2,\cdots,\frac{p-1}{2} \}$。

证明如下

首先我们知道

$(p-k)^2 \equiv (-k)^2 = k^2 \pmod{p}$

所以我们只需要考虑模$p$完系中的前$\frac{p-1}{2}$个数即可。下面我们证明对于集合$\{1,2,\cdots,\frac{p-1}{2}$中的任意两两平方模$p$都不相等。
假设存在$x,y$且$x \ne y$使得$x^2 \equiv y^2 \pmod{p}$。则有

$0 \equiv x^2-y^2 =(x-y) \cdot (x+y) \pmod{p}$

根据假设我们知道$x \ne y$所以只能$(x+y) \mid p$。但是$0<x+y<p$所以矛盾。

勒让德符号

$\left( \frac{a}{p} \right) = \begin{cases} 1 & \text{若 } a \text{ 是模 } p \text{ 的平方剩余，且 } a \not\equiv 0 \pmod{p} \\ -1 & \text{若 } a \text{ 不是模}p\text{的平方剩余} \\ 0 & \text{若 } a \equiv 0 \pmod{p} \end{cases}$

这样构造的符号体现了一个美丽的性质

$\left( \frac{a\cdot b}{p} \right)=\left( \frac{a}{p} \right)\cdot \left( \frac{b}{p} \right)$

性质1(欧拉判别)

$\left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \pmod{p}$

证明如下

首先，由于p为奇素数，由费马小定理$a^{p-1} \equiv 1 \pmod{p}$。但p-1是一个偶数所以有$(a^{\frac{p-1}{2}}-1)(a^{\frac{p-1}{2}}+1) \equiv 0 \pmod{p}$。
又p是一个素数，所以$a^{\frac{p-1}{2}}-1$和$a^{\frac{p-1}{2}}+1$必有一个是p的倍数，因此$a^{\frac{p-1}{2}}+1$模p的余数是1或-1。
情况 1：$a$ 是模 $p$ 的平方剩余
存在 $x$ 使得 $x^2 \equiv a \pmod{p}$，则：

$a^{\frac{p-1}{2}} \equiv (x^2)^{\frac{p-1}{2}} = x^{p-1} \equiv 1 \pmod{p}$

（根据费马小定理：$x^{p-1} \equiv 1 \pmod{p}$）
所以：

$\left( \frac{a}{p} \right) = 1 \equiv a^{\frac{p-1}{2}} \pmod{p}$

情况 2：$a$ 不是模 $p$ 的平方剩余
模 $p$ 的乘法群是循环群，设 $g$ 是模 $p$ 的原根，则存在整数 $r$，使得：

$a \equiv g^r \pmod{p}$

此时：

$a^{\frac{p-1}{2}} \equiv g^{r \cdot \frac{p-1}{2}} \pmod{p}$

若 $r$ 为奇数，则：

$g^{r \cdot \frac{p-1}{2}} \equiv -1 \pmod{p}$

所以：

$\left( \frac{a}{p} \right) = -1 \equiv a^{\frac{p-1}{2}} \pmod{p}$

有欧拉判别我们可以推出两个结论

$\left( \frac{-1}{p} \right) = \begin{cases} 1 & \text{若 } p\equiv 1 \pmod{4} \\ -1 & \text{若 } p \equiv 3 \pmod{4} \end{cases}$

$\left( \frac{2}{p} \right) = \begin{cases} 1 & \text{若 } p\equiv \pm1 \pmod{8} \\ -1 & \text{若 } p \equiv \pm 3 \pmod{8} \end{cases}$

性质2

设 $p$ 是满足 $p \equiv 3 \pmod{4}$ 的奇素数，若 $c$ 是模 $p$ 的平方剩余，则二次同余式：

$x^2 \equiv c \pmod{p}$

的解为：

$x \equiv \pm c^{\frac{p+1}{4}} \pmod{p}$

证明

令 $x = c^{\frac{p+1}{4}}$，则：

$x^2 = c^{\frac{p+1}{2}} = c \cdot c^{\frac{p-1}{2}}$

根据欧拉判别法，有：

$c^{\frac{p-1}{2}} \equiv \left( \frac{c}{p} \right) \pmod{p}$

若 $c$ 是平方剩余，则 $\left( \frac{c}{p} \right) = 1$，因此：

$x^2 \equiv c \pmod{p}$

得证。

性质3

设 $p, q$ 为不同的奇素数，且整数 $c$ 同时满足：

1. $c$ 是模 $p$ 的平方剩余；
2. $c$ 是模 $q$ 的平方剩余。
   则 $c$ 是模 $pq$ 的平方剩余，其解x为：

$x \equiv \pm \left( c^{\frac{p+1}{4}} \cdot q \cdot (q^{-1} \bmod p) + c^{\frac{q+1}{4}} \cdot p \cdot (p^{-1} \bmod q) \right) \pmod{pq}$

例题

Adrien’s Signs

题目

from random import randint
a = 288260533169915
p = 1007621497415251
FLAG = b'crypto{????????????????????}'
def encrypt_flag(flag):
    ciphertext = []
    plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
    for b in plaintext:
        e = randint(1, p)
        n = pow(a, e, p)
        if b == '1':
            ciphertext.append(n)
        else:
            n = -n % p
            ciphertext.append(n)
    return ciphertext
print(encrypt_flag(FLAG))

分析

难点是判断什么时候取的是正$n$什么时候取的是负$n$。对$a,p$进行简单的分析知道$p\equiv3\pmod{4}$且$\left(\frac{a}{p}\right) =1$。
根据前面的结论我们有

$\left(\frac{n}{p}\right)= \left(\frac{a^e}{p}\right) =\left(\frac{a}{p}\right)^e =1$

又根据在$p\equiv3\pmod{4}$时有$\left(\frac{-1}{p}\right) =-1$，所以

$\left(\frac{n}{p}\right) =1 \quad \quad \left(\frac{-n}{p}\right) = -1$

这样我们就能区分两者的区别。

from Crypto.Util.number import *
a = 288260533169915
p = 1007621497415251
x=[67594220461269, 501237540280788, 718316769824518, 296304224247167, 48290626940198, 30829701196032, 521453693392074, 840985324383794, 770420008897119, 745131486581197, 729163531979577, 334563813238599, 289746215495432, 538664937794468, 894085795317163, 983410189487558, 863330928724430, 996272871140947, 352175210511707, 306237700811584, 631393408838583, 589243747914057, 538776819034934, 365364592128161, 454970171810424, 986711310037393, 657756453404881, 388329936724352, 90991447679370, 714742162831112, 62293519842555, 653941126489711, 448552658212336, 970169071154259, 339472870407614, 406225588145372, 205721593331090, 926225022409823, 904451547059845, 789074084078342, 886420071481685, 796827329208633, 433047156347276, 21271315846750, 719248860593631, 534059295222748, 879864647580512, 918055794962142, 635545050939893, 319549343320339, 93008646178282, 926080110625306, 385476640825005, 483740420173050, 866208659796189, 883359067574584, 913405110264883, 898864873510337, 208598541987988, 23412800024088, 911541450703474, 57446699305445, 513296484586451, 180356843554043, 756391301483653, 823695939808936, 452898981558365, 383286682802447, 381394258915860, 385482809649632, 357950424436020, 212891024562585, 906036654538589, 706766032862393, 500658491083279, 134746243085697, 240386541491998, 850341345692155, 826490944132718, 329513332018620, 41046816597282, 396581286424992, 488863267297267, 92023040998362, 529684488438507, 925328511390026, 524897846090435, 413156582909097, 840524616502482, 325719016994120, 402494835113608, 145033960690364, 43932113323388, 683561775499473, 434510534220939, 92584300328516, 763767269974656, 289837041593468, 11468527450938, 628247946152943, 8844724571683, 813851806959975, 72001988637120, 875394575395153, 70667866716476, 75304931994100, 226809172374264, 767059176444181, 45462007920789, 472607315695803, 325973946551448, 64200767729194, 534886246409921, 950408390792175, 492288777130394, 226746605380806, 944479111810431, 776057001143579, 658971626589122, 231918349590349, 699710172246548, 122457405264610, 643115611310737, 999072890586878, 203230862786955, 348112034218733, 240143417330886, 927148962961842, 661569511006072, 190334725550806, 763365444730995, 516228913786395, 846501182194443, 741210200995504, 511935604454925, 687689993302203, 631038090127480, 961606522916414, 138550017953034, 932105540686829, 215285284639233, 772628158955819, 496858298527292, 730971468815108, 896733219370353, 967083685727881, 607660822695530, 650953466617730, 133773994258132, 623283311953090, 436380836970128, 237114930094468, 115451711811481, 674593269112948, 140400921371770, 659335660634071, 536749311958781, 854645598266824, 303305169095255, 91430489108219, 573739385205188, 400604977158702, 728593782212529, 807432219147040, 893541884126828, 183964371201281, 422680633277230, 218817645778789, 313025293025224, 657253930848472, 747562211812373, 83456701182914, 470417289614736, 641146659305859, 468130225316006, 46960547227850, 875638267674897, 662661765336441, 186533085001285, 743250648436106, 451414956181714, 527954145201673, 922589993405001, 242119479617901, 865476357142231, 988987578447349, 430198555146088, 477890180119931, 844464003254807, 503374203275928, 775374254241792, 346653210679737, 789242808338116, 48503976498612, 604300186163323, 475930096252359, 860836853339514, 994513691290102, 591343659366796, 944852018048514, 82396968629164, 152776642436549, 916070996204621, 305574094667054, 981194179562189, 126174175810273, 55636640522694, 44670495393401, 74724541586529, 988608465654705, 870533906709633, 374564052429787, 486493568142979, 469485372072295, 221153171135022, 289713227465073, 952450431038075, 107298466441025, 938262809228861, 253919870663003, 835790485199226, 655456538877798, 595464842927075, 191621819564547]
m=0
for x in x:
    if pow(x,(p-1)//2,p)==1:
        m=2*m+1
    else:
        m*=2
print(long_to_bytes(m))
#b'crypto{p4tterns_1n_re5idu3s}'

Bit by Bit

题目

from Crypto.Random import random
from Crypto.Util.number import getPrime, bytes_to_long
FLAG = b'crypto{??????????????????????????????????????????}'
def get_padding():
    seed = 256
    e = random.randint(2, q)
    padding = pow(seed, e, q)
    return padding
def public_key():
    x = random.randint(2, q)
    return pow(g, x, q)
def encrypt(m, h):
    y = random.randint(2, q)
    s = pow(h, y, q)
    c1 = pow(g, y, q)
    c2 = (s * m) % q
    return (c1, c2)
m = bytes_to_long(FLAG)
q = 117477667918738952579183719876352811442282667176975299658506388983916794266542270944999203435163206062215810775822922421123910464455461286519153688505926472313006014806485076205663018026742480181999336912300022514436004673587192018846621666145334296696433207116469994110066128730623149834083870252895489152123
g = 104831378861792918406603185872102963672377675787070244288476520132867186367073243128721932355048896327567834691503031058630891431160772435946803430038048387919820523845278192892527138537973452950296897433212693740878617106403233353998322359462259883977147097970627584785653515124418036488904398507208057206926
while m:
    padding = get_padding()
    me = padding << 1 + m % 2
    h = public_key()
    (c1, c2) = encrypt(me, h)
    print(f'(public_key={hex(h)})')
    print(f'(c1={hex(c1)}, c2={hex(c2)})')
    m //= 2

分析

难点在于需要知道$m$什么时候取0什么时候取1，这个差别关系着me的取值，这里

me=padding << (1 + m % 2)

对应着$padding \cdot 2$和$padding \cdot 4$。
如果能想到用二次剩余理论的话，大概就能想到做法，想不到就很困难。
分析题目中的数据容易知道$g$和256都是模$q$的二次剩余。

$c2=256^e \cdot k \cdot g^{xy}$

这里$k \in \{2,4\}$，进一步可以发现4是模$q$的二次剩余，而2是非二次剩余。
综上我们得到

$m= \begin{cases} 1 & \text{若 }\left( \frac{c2}{p} \right)=1\\ 0 & \text{若 }\left( \frac{c2}{p} \right)=-1 \end{cases}$

from Crypto.Util.number import *
c2_list=[...]
m=0
q = 117477667918738952579183719876352811442282667176975299658506388983916794266542270944999203435163206062215810775822922421123910464455461286519153688505926472313006014806485076205663018026742480181999336912300022514436004673587192018846621666145334296696433207116469994110066128730623149834083870252895489152123
for c2 in reversed(c2_list):
    if pow(c2,(q-1)//2,q)==1:
        m=2*m+1
    else:
        m=2*m
print(long_to_bytes(m))