RSA

ed互推

def extended_gcd(a, b):
    # 扩展欧几里得算法，返回 (gcd, x, y)，使得 a*x + b*y = gcd
    if b == 0:
        return a, 1, 0
    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return gcd, x, y

def mod_inverse(e, phi_n):
    # 求模逆
    gcd, x, _ = extended_gcd(e, phi_n)
    if gcd != 1:
        raise ValueError("e and φ(n) must be coprime")
    return x % phi_n

# 已知的 p, q, e
p = 61  # 例如
q = 53  # 例如
e = 17  # 例如

# 步骤 1: 计算 n 和 φ(n)
n = p * q
phi_n = (p - 1) * (q - 1)

# 步骤 2: 计算 d
d = mod_inverse(e, phi_n)

print(f"Private key (d) = {d}")

解密

def extended_gcd(a, b):
    """扩展欧几里得算法，返回 gcd, x, y 使得 a*x + b*y = gcd"""
    if b == 0:
        return a, 1, 0
    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return gcd, x, y

def mod_inverse(e, phi_n):
    """求 e 关于 phi_n 的模逆"""
    gcd, x, _ = extended_gcd(e, phi_n)
    if gcd != 1:
        raise ValueError("e 和 φ(n) 必须互质")
    return x % phi_n

def rsa_decrypt(ciphertext, d, n):
    """使用私钥 d 和模数 n 解密密文"""
    return pow(ciphertext, d, n)

# 给定的 RSA 参数
p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

# 计算 RSA 模数 n 和 φ(n)
n = p * q
phi_n = (p - 1) * (q - 1)

# 计算私钥 d
d = mod_inverse(e, phi_n)
print(f"RSA 私钥 d = {d}")

# 解密密文
plaintext = rsa_decrypt(c, d, n)
print(f"解密后的明文 (整数表示) = {plaintext}")

# 如果明文是 ASCII 编码的文本，可以进一步转换为字符
# 这里假设明文是一个数字，表示原始消息

共模攻击

def extended_gcd(a, b):
    """扩展欧几里得算法，返回 gcd, x, y 使得 a*x + b*y = gcd"""
    if b == 0:
        return a, 1, 0
    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return gcd, x, y

def mod_inverse(a, n):
    """求 a 关于 n 的模逆"""
    gcd, x, _ = extended_gcd(a, n)
    if gcd != 1:
        raise ValueError(f"{a} 和 {n} 不是互质的，模逆不存在")
    return x % n

def common_modulus_attack(c1, e1, c2, e2, n):
    """共模攻击"""
    # 扩展欧几里得算法，找到 x 和 y
    gcd, x, y = extended_gcd(e1, e2)
    if gcd != 1:
        raise ValueError("e1 和 e2 必须互质")
    
    # 处理负指数
    if x < 0:
        c1 = mod_inverse(c1, n)
        x = -x
    if y < 0:
        c2 = mod_inverse(c2, n)
        y = -y

    # 计算明文
    m = (pow(c1, x, n) * pow(c2, y, n)) % n
    return m

# 给定参数
c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1 = 11187289
c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2 = 9647291

# 执行共模攻击
m = common_modulus_attack(c1, e1, c2, e2, n)
print(f"解密后的明文（整数表示）: {m}")