Rabin加密

[NSSRound#11 Basic]ez_signin

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

p = getPrime(512)
q = getPrime(512)
assert p > q
n = p*q
e = 65536
m = bytes_to_long(flag)
num1 = (pow(p,e,n)-pow(q,e,n)) % n
num2 = pow(p-q,e,n)
c = pow(m,e,n)

print("num1=",num1)
print("num2=",num2)
print("n=",n)
print("c=",c)

我的解答

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

num1= 272862669171474396396346320044652981819641446895896259048760571202880701946816194621292378789553813990527252202593627409090108658126752853095133937756584319743618683075636273175295512837302880904708130820889988379507919111761986607349784417775005751393682844805190426434696242078340475392961106508937811566
num2= 34232812347968455856831076583522084771897754029863151152576650134413405663246929271965499563534059810310755948919124902737740910396366145723725169679562125884220944285623073035973389322178917320950312088905211769141473722907668799740465400147776589294849843633307848989273671006177136460638863297454577348372
n= 101041915402371268562539864391230558209018773341751828731097302946455960816468442318971537237532932589285827603020517675291956691309668029525760296017908673381150418459764499447724506114116163197166174909161359478495861591920749082693491285803326797990496585528516999626793686927001772331673338109924364148573
c= 98498440419285405132379532222038197349093970292969688148442636409863654318610296605795615484920674902479244901779412903340424597753355605790140770272076966193568118040994956336580247900526084471936779882586951112711099502637426488794349726185073973638506930983094554968102888784905597559122745754481155302566
e = 65536

p=gcd(num1+num2,n)
assert n%p==0
q=n//int(p)

for i in range(16):
    c1=pow(c,(p+1)//4,p)
    c2=pow(c,(q+1)//4,q)
    c=crt([int(c1),int(c2)],[p,q])
print(long_to_bytes(c))

Cipolla算法

过程

代码实现

def square_root_of_quadratic_residue(n, modulo):
    def generate_quadratic_field(d, modulo=0):
        class QuadraticFieldNumber:
            def __init__(self, x, y):
                self.x = x % modulo
                self.y = y % modulo

            def __mul__(self, another):
                x = self.x * another.x + d * self.y * another.y
                y = self.x * another.y + self.y * another.x
                return self.__class__(x, y)

            def __pow__(self, exponent):
                result = self.__class__(1, 0)
                if exponent:
                    temporary = self.__class__(self.x, self.y)
                    while exponent:
                        if exponent & 1:
                            result *= temporary
                        temporary *= temporary
                        exponent >>= 1
                return result

            def __str__(self):
                return '({}, {} \\sqrt({}))'.format(self.x, self.y, d)

        return QuadraticFieldNumber

    if modulo == 2:
        return 1
    if n % modulo == 0:
        return 0
    Legendre = lambda n: pow(n, modulo - 1 >> 1, modulo)
    if Legendre(n) == modulo - 1:
        return -1
    t = 0
    while Legendre(t ** 2 - n) != modulo - 1:
        t += 1
    w = (t ** 2 - n) % modulo
    return (generate_quadratic_field(w, modulo)(t, 1) ** (modulo + 1 >> 1)).x

def convert_to_base(n, b):
    if n < 2:
        return [n]

    temp = n
    ans = []

    while temp != 0:
        ans = [temp % b] + ans
        temp //= b

    return ans


def cipolla(n, p):
    n %= p

    if n == 0 or n == 1:
        return [n, (p - n) % p]

    phi = p - 1

    if pow(n, phi // 2, p) != 1:
        return []

    if p % 4 == 3:
        ans = int(pow(n, (p + 1) // 4, p))
        return [ans, (p - ans) % p]

    aa = 0
    for i in range(1, p):
        temp = pow(((i * i - n) % p), phi // 2, p)

        if temp == phi:
            aa = i
            break

    exponent = convert_to_base((p + 1) // 2, 2)

    def cipolla_mult(ab, cd, w, p):
        a, b = ab
        c, d = cd
        return (a * c + b * d * w) % p, (a * d + b * c) % p

    x1 = (aa, 1)
    x2 = cipolla_mult(x1, x1, aa * aa - n, p)

    for i in range(1, len(exponent)):
        if exponent[i] == 0:
            x2 = cipolla_mult(x2, x1, aa * aa - n, p)
            x1 = cipolla_mult(x1, x1, aa * aa - n, p)
        else:
            x1 = cipolla_mult(x1, x2, aa * aa - n, p)
            x2 = cipolla_mult(x2, x2, aa * aa - n, p)
    return [x1[0], (p - x1[0]) % p]