basic ring¶

群，环，域的基本概念 ¶

https://ctf-wiki.org/crypto/basic/introduction/

https://doc.sagemath.org/html/en/tutorial/tour_rings.html

the integers {...,−1,0,1,2,...}, called ZZ in Sage.
the rational numbers – i.e., fractions, or ratios, of integers – called QQ in Sage.
the real numbers, called RR in Sage.
the complex numbers, called CC in Sage.

使用示例 ¶

浙江省第七届大学生信息安全竞赛 myez_encode

from Crypto.Util.number import bytes_to_long, getPrime
from sympy import isprime
import random
from flag import flag


def generate_ecc_parameters():
    """随机生成两个 2^512 大数"""
    x = random.randint(1, 1 << 512)
    y = random.randint(1, 1 << 512)
    return x, y


def find_prime_on_curve(x, y, a, b, ecc_p):
    """以 x,y 为初始值寻找素数点"""
    p = x
    q = y
    while not (isprime(p) and isprime(q)):
        p = random.randint(2, ecc_p - 1)
        q = (p**3 + a * p + b) % ecc_p
    return p, q


def generate_rsa_parameters():
    a = getPrime(512)
    b = getPrime(512)
    ecc_p = getPrime(512)
    x, y = generate_ecc_parameters()  # 无用
    p, q = find_prime_on_curve(x, y, a, b, ecc_p)
    n = p * q
    print(f"p= {p}\nq= {q}\nn= {n}")
    print(f"a= {a}\nb= {b}")
    print(f"P= {ecc_p}")


if __name__ == "__main__":
    generate_rsa_parameters()
# n = p*q = p*(p**3+a*p+b)% P
n = p * q
e = 9
m = bytes_to_long(flag)
c = pow(m, e, n)
print(c)

"""
n= 23298836191712395990541254600776262066247692725919114528027158820049802443474994576179738462067629079873633948850637889127452791527914591229415148712172587856497614285410824614070907847594399218298016379507879066220104597707859246179921731928508884947347652904142879813069359815823184922170241099916465722623
a= 7388665644223916915334064243181348811184637180763467245762518813757790945069068654378380490110607063038613823004593920489924786053478102905200169738195523
b= 11742940161647091720180482697980016011774828087234021441133595442949631197989696508358388255191793888646498553804646435609849154496274569000398776043150743
P= 11300086101709077144191286182913849072593185125745291892398153828719453495325025227858328617077648296782357912556752467026523366682963139253552060862229027
c= 9314530945343661153059846131608414257092556390479105017633636336832925597262814680689800448223193301814365726128618348603188219757245073917910487794768758461683644600756896595336654006282030911824869219015400826589122838492456940861634378619000373353637666835642505021355710338342048772713981673863167110471
"""

In [1]:

Copied!





from sage.all import *

# Given values
e = 9
n = 23298836191712395990541254600776262066247692725919114528027158820049802443474994576179738462067629079873633948850637889127452791527914591229415148712172587856497614285410824614070907847594399218298016379507879066220104597707859246179921731928508884947347652904142879813069359815823184922170241099916465722623
a = 7388665644223916915334064243181348811184637180763467245762518813757790945069068654378380490110607063038613823004593920489924786053478102905200169738195523
b = 11742940161647091720180482697980016011774828087234021441133595442949631197989696508358388255191793888646498553804646435609849154496274569000398776043150743
P = 11300086101709077144191286182913849072593185125745291892398153828719453495325025227858328617077648296782357912556752467026523366682963139253552060862229027
c= 9314530945343661153059846131608414257092556390479105017633636336832925597262814680689800448223193301814365726128618348603188219757245073917910487794768758461683644600756896595336654006282030911824869219015400826589122838492456940861634378619000373353637666835642505021355710338342048772713981673863167110471
# PR.<x> = PolynomialRing(GF(P))
PR.<x> = Zmod(P)[ ]
# n = p * q where q = (p^3 + a*p + b) mod P
# n = p * (p^3 + a*p + b) mod P
poly = x * (x^3 + a*x + b) - n

# Find roots
p = poly.roots()[0][0]
p = int(p) # 注意转变为python的int类型
q = n/p
print(f"p = {p}, q = {q}")
##### RSA #####
# c = pow(m, e, n)
# m = pow(c, inverse_mod(e, euler_phi(n)), n)

# k = inverse_mod(e, (q-1)*(p-1)) # ZeroDivisionError
# m = pow(c, k, n)
## 这里 euler_phi(n) 比较难算，而且我们分解后发现并不存在逆元
k = inverse_mod(e, euler_phi(q))
m = pow(c, k, q)
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(m)) # b'DASCTF{Very_easy_3NC0dE_Is_1t}'
from sage.all import *

# Given values
e = 9
n = 23298836191712395990541254600776262066247692725919114528027158820049802443474994576179738462067629079873633948850637889127452791527914591229415148712172587856497614285410824614070907847594399218298016379507879066220104597707859246179921731928508884947347652904142879813069359815823184922170241099916465722623
a = 7388665644223916915334064243181348811184637180763467245762518813757790945069068654378380490110607063038613823004593920489924786053478102905200169738195523
b = 11742940161647091720180482697980016011774828087234021441133595442949631197989696508358388255191793888646498553804646435609849154496274569000398776043150743
P = 11300086101709077144191286182913849072593185125745291892398153828719453495325025227858328617077648296782357912556752467026523366682963139253552060862229027
c= 9314530945343661153059846131608414257092556390479105017633636336832925597262814680689800448223193301814365726128618348603188219757245073917910487794768758461683644600756896595336654006282030911824869219015400826589122838492456940861634378619000373353637666835642505021355710338342048772713981673863167110471
# PR. = PolynomialRing(GF(P))
PR. = Zmod(P)[ ]
# n = p * q where q = (p^3 + a*p + b) mod P
# n = p * (p^3 + a*p + b) mod P
poly = x * (x^3 + a*x + b) - n

# Find roots
p = poly.roots()[0][0]
p = int(p) # 注意转变为python的int类型
q = n/p
print(f"p = {p}, q = {q}")
##### RSA #####
# c = pow(m, e, n)
# m = pow(c, inverse_mod(e, euler_phi(n)), n)

# k = inverse_mod(e, (q-1)*(p-1)) # ZeroDivisionError
# m = pow(c, k, n)
## 这里 euler_phi(n) 比较难算，而且我们分解后发现并不存在逆元
k = inverse_mod(e, euler_phi(q))
m = pow(c, k, q)
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(m)) # b'DASCTF{Very_easy_3NC0dE_Is_1t}'

p = 2925490712948356009205547798331037409204468852265154197929696123102317330847028997592576845375767951888373634075473448002921250636926630905567362014595493, q = 7964077988212602731598828926489143570796450850963162530397620970577507270219530635660167912693046701894468774510746807002256765035407708129322533385075411
b'DASCTF{Very_easy_3NC0dE_Is_1t}'