526互联

cryptohack wp day(6)

发布时间 2023-05-09 00:26:14作者: Cryglz

公钥密码学

在做这部分之前，先来了解下什么时公钥密码学吧
公钥密码学是一种密码学分支，它涉及使用加密算法和密钥对数据进行加密和解密。与对称密钥加密不同，公钥密码学使用两个密钥：一个公钥和一个私钥，因此也称为非对称密钥加密。

在公钥密码学中，公钥是公开的，可以向任何人公开，私钥则由接收方保管。加密过程中，发送方使用接收方的公钥对数据进行加密，接收方使用其私钥对数据进行解密。

公钥密码学广泛应用于安全通信、数字签名、数字证书和密钥交换等领域。最常见的公钥密码学算法包括RSA、Diffie-Hellman密钥交换、椭圆曲线密码等。

第一题（RSA Starter 1)

先来了解先RSA吧：
RSA是一种公钥密码学算法，其名称源自于发明者Ron Rivest、Adi Shamir和Leonard Adleman的姓氏。RSA算法使用两个大素数和它们的乘积作为公钥和私钥的组成部分，因此也被称为“RSA公钥加密”。

RSA算法的安全性基于一个数论问题：质因数分解。具体地说，RSA加密过程中，发送方使用接收方的公钥对消息进行加密，接收方使用其私钥对密文进行解密。在加密过程中，发送方使用一个公钥指数来加密消息，并将其发送给接收方。接收方使用其私钥来解密该消息，从而获得原始消息。

RSA算法具有许多优点，其中之一是可以安全地传输密钥，因为在使用RSA算法之前，接收方可以通过非保密通道安全地传输其公钥。此外，RSA算法还可以用于数字签名，以验证消息的来源和完整性。

尽管RSA算法在许多情况下都被广泛使用，但它仍存在某些安全性问题。例如，使用较小的密钥长度或不合适的加密模式可能导致RSA算法易受到攻击。因此，在实际应用中，需要谨慎考虑RSA算法的安全性和实现。

想更好的了解RSA，我这里推荐下两位大佬的博客：[(https://www.cnblogs.com/hykun/p/RSA.html)]，https://www.tr0y.wang/2017/11/06/CTFRSA/index.html

计算（10117 mod 22663）
print((pow(101,17,22663)))

第二题（RSA Starter 2）

m =12
e = 65537
p = 17
q = 23
n = p*q
print(pow(m,e,n))

第三题（RSA Starter 3）


求欧拉函数fn

fn =(p-1)*(q-1)
print(fn)

第四题（RSA Starter 4）


求私钥d

import gmpy2
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537
fn = (p-1)*(q-1)
d = gmpy2.invert(e,fn)#求e的逆元d
print(d)

第五题（RSA Starter 5）


给了n,e,c,要想得到明文m,先得求出私钥d,要想求出d,先得求出fn,要想知道fn,得先知道p,q，由于p*q = n，且p和q互素，所以我们可以分解n
这里推荐一个分解大素数挺好用的一个网站http://factordb.com/

import gmpy2
p = 857504083339712752489993810777#分解后的p和q
q =  1029224947942998075080348647219
e = 65537
c = 77578995801157823671636298847186723593814843845525223303932
fn = (p-1)*(q-1)
n = p*q
d = gmpy2.invert(e,fn)
print(d)
m =pow(c,d,n)
print(m)

第六题（RSA Starter 6）


本题主要是了解RSA签名：
RSA签名是RSA算法的一种应用，它用于数字签名，以验证消息的来源和完整性。RSA签名可以分为两个步骤：签名和验证。

在签名过程中，签名者使用其私钥对消息进行签名。具体地说，签名者将消息哈希为一个固定长度的值，然后使用其私钥对该值进行加密，从而生成签名。接收方可以使用签名者的公钥对签名进行解密，并验证签名是否与原始消息匹配。

RSA签名的安全性基于RSA算法的离散对数问题，即找到两个大素数的乘积的质因数分解。由于该问题的计算复杂度非常高，因此RSA签名在许多情况下都被认为是安全的。

RSA签名被广泛应用于数字证书、电子商务和安全通信等领域。但需要注意的是，在实际应用中，必须谨慎地选择RSA密钥长度和哈希算法，以确保签名的安全性。
解题代码如下：

from hashlib import sha256
from Crypto.Util.number import *
N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
m = b'crypto{Immut4ble_m3ssag1ng}'
H = bytes_to_long(sha256(m).digest())
s = pow(H,d,N)
print((s))

第七题（Factoring）


这题主要考分解大素数，正如前面所说，可以使用factordb.com网站进行分解，也可以安装库：pip install factordb-python，然后直接命令行分解：

或者使用yafu：

也可以使用python，以下是python代码：

from factordb.factordb import FactorDB
f = FactorDB(510143758735509025530880200653196460532653147)
print(f.get_factor_list())
print(f.connect())
print(f.get_factor_list())

第八题（Monoprime）

对于一个素数 p pp，它的欧拉函数值 φ ( p ) = p − 1
代码：

import gmpy2
import libnum
import binascii
from Crypto.Util.number import *
n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942

d = gmpy2.invert(e,(n-1))
flag = pow(ct,d,n)
print(flag)
print(libnum.n2s(int(flag)))
print(bytes.fromhex(hex(flag)[2:]))
print(binascii.unhexlify(hex(flag)[2:]))
print(binascii.a2b_hex(hex(flag)[2:]))
print(long_to_bytes(flag))