RSA encryption algorithm analysis

I participated in a CTF competition a few months ago. I encountered the RSA encryption and decryption question. It was also a fog at the time. After the game, I found the data and sorted it out.

Algorithm Introduction

The RSA encryption algorithm belongs to the public key encryption algorithm and is an asymmetric cryptographic algorithm. The so-called asymmetric is that one password is used for encryption and the other is used for decryption. In general, public key encryption, private key decryption, and of course Other cases.

Algorithm Principle

The RSA algorithm is based on the fact that it is very easy to multiply two large prime numbers, but it is extremely difficult to factorize the product, so the product can be exposed as an encryption key. RSA algorithm three parameters: n, e1, e2

n=pq (p, q is 2 large prime numbers) The number of bits occupied by the binary of n is the length of the secret key.
E1 and e2 are a pair of related values, e1 can be arbitrarily taken, but e1 and (p-1)
(q-1) are required to be homogeneous; (e2e1)mod((p-1)(q- 1))=1.
(n, e1), (n, e2) is the key pair, where (n, e1) is the public key and (n, e2) is the private key.

Algorithm Formula

Assumption:
A: Clear text
B: ciphertext

——Use public key encryption formula ——
A=B^e2 mod n
B=A^e1 mod n

——Use private key encryption formula ——
A=B^e1 mod n
B=A^e2 mod n

Actual demonstration

Summary of topics

This is a public key encryption, public key decryption RSA topic
The public key password is given as: {920139713, 19}, where 920139713 is n and 19 is e1.
The ciphertext B to be decrypted is:
704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
……
Finally solve the value of private key A?

Problem Solving

List formula: public key encryption
Assumption:
A: Clear text
B: ciphertext
A=B^e2 mod n
B=A^e1 mod n

This question gives B, n, e1, and finds the value of A, which can be solved by taking Equation 2.

Write code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import string
Strs=string.digits+string.lowercase #List a-z numbers
f=open("data.txt") #Write the contents of ciphertext B into data.txt for the program to read.
data=f.readlines()
f.close()
plaintext=""
For b in data: #Remove all ciphertexts (b)
For a in strs: #Remove all possible plaintexts (a)
If ord(a)**19 % 920139713==int(b.strip()): #ord Convert a string to an ascii code
plaintext+=a
print plaintext
operation result

flag13212je2ue28fy71w8u87y31r78eu1e2

本文标题:RSA encryption algorithm analysis

文章作者:nmask

发布时间:2016年09月06日 - 00:09

最后更新:2019年08月16日 - 15:08

原始链接:https://thief.one/2016/09/06/RSA encryption algorithm analysis/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

nmask wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!

热门文章推荐: