Modular Arithmetic

Adrien's Signs

Adrien's been looking at ways to encrypt his messages with the help of symbols and minus signs. Can you find a way to recover the flag?

Challenge files:
- source.py
- output.txt

Enter flag here: crypto{FLAG}

知识:

完全积性：

$(\frac{ab}{p})=(\frac{a}{p})(\frac{b}{p})$

Solve

$(\frac{a}{p})=1$

if $b == 1$:$(\frac{n}{p})=(\frac{a}{p})^{e}=1$

else:$(\frac{n}{p})\neq1$

Exp

from gmpy2 import *
from Crypto.Util.number import *

enc = 

a = 
p = 

print(jacobi(a, p))

plaintext = ""

for i in enc:
    if jacobi(i, p) == 1:
        plaintext += "1"
    else:
        plaintext += "0"

print(long_to_bytes(int(plaintext,2)).decode())

Modular Binomials

Rearrange the following equations to get the primes p,q

$$ N=p⋅q\\ c_1=(2⋅p+3⋅q)^{e1}\mod N\\ c_2=(5⋅p+7⋅q)^{e2}\mod N $$

Challenge files:
- data.txt

Solve

$$ p = \gcd(7^{e_1\cdot e_2}\cdot c_1^{e_2} - 3^{e_1\cdot e_2}\cdot c_2^{e_1}, N) $$

Exp

from gmpy2 import gcd

N = 
e1 = 
e2 = 
c1 = 
c2 = 

E = e1*e2
temp = pow(7, E, N)*pow(c1, e2, N) - pow(3, E, N) * pow(c2, e1, N) % N

p = gcd(temp, N)
q = N // p
assert p*q == N
print("crypto{"+str(p)+","+str(q)+"}")