信息加密与验证

How can you ensure that the person receiving your message knows that you wrote it?

You’ve been asked out on a date, and you want to send a message telling them that you’d love to go, however a jealous lover isn’t so happy about this.

When you send your message saying yes, your jealous lover intercepts the message and corrupts it so it now says no!

We can protect against these attacks by signing the message.

Imagine you write a message M. You encrypt this message with your friend’s public key: C = Me0 mod N0.

To sign this message, you calculate the hash of the message: H(M) and “encrypt” this with your private key: S = H(M)d1 mod N1.

Your friend can decrypt the message using their private key: m = Cd0 mod N0. Using your public key they calculate s = Se1 mod N1.

Now by computing H(m) and comparing it to s: assert H(m) == s, they can ensure that the message you sent them, is the message that they received!

In real cryptosystems, it’s best practice to use separate keys for encrypting and signing messages.

大意就是给了一个消息，对其用朋友的公钥加密，让朋友用朋友的私钥解密获得原消息

同时，对消息的HASH值用自己的私钥加密，让朋友用自己的公钥解密，并与获得的消息的HASH值比对

如果HASH值相同，那就说明消息并没有被篡改

1
2
ooo = bytes_to_long(hashlib.sha256(flag).digest())
answer = long_to_bytes(pow(ooo, d, N)).hex()

由于HASH加密后的值无法进行计算，所以我们需要先用.digest()将其转换成bytes形式，再将bytes转化成可以计算的Long整型值。

查看n的素因子

遇到了一个N， 可以先去factordb.com查看一下N的素因子是否曾被记录，若可被完全分解，知道了p和q，那么问题就迎刃而解了

小公钥指数攻击：

e=1

由于gmpy2.invert(1, k)对于任意的 K， 得到的结果都为 1

则我们可以直接print(long_to_bytes(pow(c, 1, n)))得到结果

e很小，且c 远远小于 n

即说明 flag ** e = c, 可推出结果

低解密指数攻击：

Wiener’s Attack

在RSA中d也称为解密指数，当d比较小的时候，e也就显得特别大了。

适用情况：e过大或过小（一般e过大时使用）

可以使用附件RSA工具里的rsa-wiener-attack-master

在 d 比较小（d < 1/3 * N ** 1 / 4）时，攻击者可以使用 Wiener’s Attack 来获得私钥。

Boneh attack

image-20211008225355445

image-20211008225643406

由于公钥e的选取和 φ(N)的大小差不多，所以k的大小和d的大小差不多，于是有

image-20211008225759836

image-20211008230006142

Then the vector image-20211008230033466is a short vector of the lattice, under the assumption that d is very low. Applying a lattice reduction (see the CryptoHack challenge Gaussian Reduction to implement it yourself, or use LLL), this vector can be found, and d can be extracted from its second coordinate.

下面是使用 SageMath version 9.1的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
N = 0x665166804cd78e8197073f65f58bca14e019982245fcc7cad74535e948a4e0258b2e919bf3720968a00e5240c5e1d6b8831d8fec300d969fccec6cce11dde826d3fbe0837194f2dc64194c78379440671563c6c75267f0286d779e6d91d3e9037c642a860a894d8c45b7ed564d341501cedf260d3019234f2964ccc6c56b6de8a4f66667e9672a03f6c29d95100cdf5cb363d66f2131823a953621680300ab3a2eb51c12999b6d4249dde499055584925399f3a8c7a4a5a21f095878e80bbc772f785d2cbf70a87c6b854eb566e1e1beb7d4ac6eb46023b3dc7fdf34529a40f5fc5797f9c15c54ed4cb018c072168e9c30ca3602e00ea4047d2e5686c6eb37b9
e = 0x2c998e57bc651fe4807443dbb3e794711ca22b473d7792a64b7a326538dc528a17c79c72e425bf29937e47b2d6f6330ee5c13bfd8564b50e49132d47befd0ee2e85f4bfe2c9452d62ef838d487c099b3d7c80f14e362b3d97ca4774f1e4e851d38a4a834b077ded3d40cd20ddc45d57581beaa7b4d299da9dec8a1f361c808637238fa368e07c7d08f5654c7b2f8a90d47857e9b9c0a81a46769f6307d5a4442707afb017959d9a681fa1dc8d97565e55f02df34b04a3d0a0bf98b7798d7084db4b3f6696fa139f83ada3dc70d0b4c57bf49f530dec938096071f9c4498fdef9641dfbfe516c985b27d1748cc6ce1a4beb1381fb165a3d14f61032e0f76f095d
c = 0x503d5dd3bf3d76918b868c0789c81b4a384184ddadef81142eabdcb78656632e54c9cb22ac2c41178607aa41adebdf89cd24ec1876365994f54f2b8fc492636b59382eb5094c46b5818cf8d9b42aed7e8051d7ca1537202d20ef945876e94f502e048ad71c7ad89200341f8071dc73c2cc1c7688494cad0110fca4854ee6a1ba999005a650062a5d55063693e8b018b08c4591946a3fc961dae2ba0c046f0848fbe5206d56767aae8812d55ee9decc1587cf5905887846cd3ecc6fc069e40d36b29ee48229c0c79eceab9a95b11d15421b8585a2576a63b9f09c56a4ca1729680410da237ac5b05850604e2af1f4ede9cf3928cbb3193a159e64482928b585ac
s = floor(sqrt(N))
M = Matrix([[e, s], [N, 0]])
Mred = M.LLL()
D = [abs(Mred[i, 1]) // s for i in [0,1]]
for d in D:
    t = randint(2, N - 2)
    tt = pow(t, e, N)
    if tt^d != t:
        continue
    flag = int(pow(c, d, N))
    flag = flag.to_bytes((flag.bit_length() + 7)//8, 'big')
    print(f'FLAG: {flag.decode()}')