AAA CTF101 安全攻防实践短学期 Crypto Lab 1

实验指导

仅供参考。

Task 1

逃课写法：

from math import gcd  # gcd


def inverse(x, n):
    return pow(x, -1, n)

造轮子写法：

def exgcd(x, y):
    if y:
        a, b, r = exgcd(y, x % y)
        return b, a - (x // y) * b, r
    return 1, 0, x


def gcd(x, y):
    return exgcd(x, y)[2]


def inverse(x, n):
    return exgcd(x, n)[0] % n

Task 2

只写了前两个比较好写的，BabyDLP 因为不想学数学了所以摆了（orz

第一个就是 RSA，$e = 2^{30} + 3$，可以直接用 Sage 的 factor() 解决

ccpc.py

#!/usr/bin/env sage
from sage.all import *


e = (1 << 30) + 3

for i in range(int(input())):
    n, c = map(int, input().split())

    (p, _), (q, _) = factor(n)

    assert p * q == n

    m = (p - 1) * (q - 1)
    assert gcd(m, e) == 1

    d = pow(e, -1, m)
    x = pow(c, d, n)
    print(f'Case {i + 1}: {x}')

第二个是较简单的离散对数，可以直接用 discrete_log() 一把梭

hdu.py

#!/usr/bin/env sage
from sage.all import *


for i in range(int(input())):
    p, a, b = map(int, input().split())

    G = GF(p)
    try:
        print(discrete_log(G(b), G(a)))
    except ValueError:
        print(-1)