当前位置：网站首页>RSA basic principle and common attack methods
RSA basic principle and common attack methods
20220115 02:27:46 【Xiao Xiangzi】
1 Preface
Cryptography is the processing of data 、 Storage and communication procedures provide additional levels of security . In recent years , Mathematicians and computer scientists have developed a series of increasingly complex algorithms , These algorithms are designed to ensure confidentiality 、 integrity 、 Authentication and non repudiation . While cryptologists spend a lot of time developing strong encryption algorithms , Hackers and the government have invested considerable resources to crack these cryptographic algorithms . This gives rise to the field of cryptography " The arms race ", And led to the continuous development of extremely sophisticated algorithms used today .
2 In modern cryptography RSA
“ Modern cryptography ” The subject of can be divided into “ symmetric cryptography ” and “ Asymmetric cryptography ”.
The symmetric key algorithm relies on a " Shared secrets " Encryption key , The key will be distributed to all members participating in the communication . All communication members use this key to encrypt and decrypt messages , Therefore, both sender and receiver have copies of the shared key . Both sides of the communication will use the same key to encrypt and decrypt the message . When using a long key , Symmetric encryption is difficult to crack . Symmetric key algorithm is mainly used to perform batch encryption , And only provide confidentiality for security services . Symmetric key cryptography is also called secret key cryptography 、 Private key cryptography 、 Session key cryptography 、 Shared secret key cryptography .
The following figure shows the encryption and decryption process of symmetric key .
Symmetric key cryptography has the following weaknesses :
Key distribution is a major problem . Before establishing communication using symmetric key protocol , Communication participants must have a method of securely exchanging keys . If there is no secure electronic channel available , Then you often have to use offline key distribution methods ( Is no longer part of the exchange ) .
Symmetric key cryptography well does not realize non repudiation . Because any communication party can use the shared key to encrypt and decrypt the message , Therefore, the source of the specified message cannot be distinguished .
This algorithm is not scalable . For large user groups , It is very difficult to communicate with symmetric key cryptography . Only if each possible combination of users shares a private key , Only secure and proprietary communication between individuals in the group can be achieved .
The key must be updated frequently . Whenever a member leaves the user group , All keys involving this member must be discarded .
Asymmetric key algorithm is also called public key algorithm , It provides a solution to the weakness of symmetric key encryption . In this system , Each user has two keys : A public key shared among all users , And another private key that only the user knows and keeps . But the unexpected thing is : The opposite and related keys must be applied successively to encryption and decryption . let me put it another way , If you use a public key to encrypt a message , Then only the relevant private key can be decrypted , vice versa .
chart 6.4 This paper explains the encryption and decryption of messages in public key cryptosystem 、 The algorithm used .
sender The recipient
Consider this example : If Alice Want to use public key cryptography to Bob Send a message , She first generated this message , Subsequent use Bob The public key of the message is encrypted . The only possible way to decrypt this ciphertext is to use Bob The private key , And the only user who has the right to use this key is Bob, therefore , Alice After encrypting the message , You can't even decrypt this message . If Bob Hope to Alice Send a response message , He can use Ali The response message is encrypted with the public key of the socket , Alice The message can then be decrypted using her own private key , To read these messages .
Once the sender encrypts the message with the recipient's public key , So in Don't know the recipient's private key ( The public key used to generate the message / The other half of the private key pair ) Under the circumstances , No users ( Including the sender ) Can decrypt this information . This is the advantage of public key cryptography , That is, the public key can be freely shared using an insecure communication channel , And create a secure communication channel between previously unknown users .
RSA It is the most widely used asymmetric encryption algorithm . It plays an extremely important role in modern cryptography , If you want to choose a representative cryptography algorithm for indepth research , I recommend you study RSA Algorithm .
3 Fundamentals of Mathematics
RSA Summary of mathematical knowledge about algorithms
3.1 Mutual relationship
If two positive integers , except 1 There is no common factor other than , We call these two numbers Mutual relationship , such as 4 and 15
3.2 Euler function
Any given positive integer n, If it is less than or equal to n In the positive integer of , How many are related to n Constitute a reciprocal relationship ？ such as 10 How many positive integers within are associated with 10 What about mutuality ？ The way to calculate this value is called Euler function , With φ(n) Express ,φ(10)=4. If p,q All prime numbers ,φ(p*q) = (p1)(q1).
give an example ： p=3,q=5, And 15 The number of Coprime is 1,2,4,7,8,11,13,14, You can count out a total of 8 individual , At the same time, it can also be calculated by formula φ(15) = (31)*(51)=8.
3.3 Euler theorem
Euler theorem ： If two positive integers a and n Coprime , be n The Euler function of φ(n) Let the following equation hold ：
in other words ,a Of φ(n) The inferior is n The remainder of the division is 1. Or say ,a Of φ(n) To the power of 1, Can be n to be divisible by .
give an example ：3 and 7 Coprime , and 7 The Euler function of φ(7) be equal to 6, therefore 3 Of 6 Power （729） subtract 1, Can be 7 to be divisible by （728/7=104）.
3.4 Modular inverse elements
If two positive integers e and n Coprime , Then we can find the whole number d, bring e * d  1 By n to be divisible by , Or say e * d By n The remainder of the division is 1. At this time ,d It's called e Of “ Modular inverse elements ”. Euler's theorem can be used to prove the existence of module anti elements .(python: d = gmpy2.invert(e,φ(n)))
4RSA Algorithm
The most famous public key cryptosystem is named after its Creator .1 977 year , Ronald Rivest、Adi Shamir and Leonard Adleman Put forward RSA Public key algorithm , This algorithm has become the standard still used all over the world today . They patented the algorithm and set up a commercial company (RSA Safety company ), The company develops mainstream products using its security technology . today , RSA Algorithms have formed many wellknown security infrastructures ( for example Microsoft、Nokia and Cisco The company's corresponding products ) The security framework .RSA The length of the secret key is not fixed .
4.1RSA Algorithm calculation steps
RSA The algorithm relies on the inherent computational difficulty of large numbers in factorization . Each user's public key and system's private key are described in the following steps :
（1） Choose two large prime numbers , Calculate the modulus N = p * q
（2） Calculating Euler function φ(N) = (p1) * (q1), Then choose one e(1<e<φ), also e and φ Coprime
（3） seek e The modulo inverse of d, The calculation method is as follows :e * d ≡ 1 (mod φ)
（4） The clear m To encrypt ：c = m^e mod N, You can get ciphertext c.
（5） To ciphertext c To decrypt ：m = c^d mod N, You can get plaintext m.
Arrangement ：
p and q： Two large prime numbers , It's another parameter N Two factors of .
N： Large integer , It can be called modulus
e and d： Modular inverse number
c and m： Ciphertext and plaintext
(N, e)： Public key
(N, d)： Private key
Key length ：n The number of bits in binary , For example, the key length is 512 representative n The length expressed in binary is 512bit.
Verify the calculation ：
1. Suppose the ciphertext Xiao Ming wants to send is m=12
2. Then Xiao Ming randomly selects two coprime numbers p=3,q=5, be n=15, φ(n)=(31)*(51)=8
3. stay 1~8 Choose one at random from 8 Coprime number as public key e, Suppose Xiao Ming chooses e=3, be (15, 3) For public key
4. So according to e *d%8=1, You can work out d=19, be (15,3) For public key ,(15,19) For private key
5. When encrypting ：
The ciphertext actually sent is ：12^3%15=3
7. When decrypting ：
The received ciphertext is 3 after , Decipherment : 3^19%15=1162261467%15=12
4.2 RSA Some questions about the algorithm
problem 1: If everyone needs a different prime number , Won't you run out of prime numbers ？
answer ： Can't , according to “ Prime number theorem ”, Less than n The total number of prime numbers of is about n/ln(n).
problem 2：: Will two people accidentally choose the same prime number ？
answer ： It seldom happens . from M Choose from a prime number q Prime number , The probability that at least two prime numbers are the same reaches 1/2,q Need to achieve 1.17 *M^(1/2).
problem 3： Is it difficult to produce prime numbers ？
answer ： No difficulty . Consult the information to know , Generally, an odd number is randomly generated first n, Then use some prime detection algorithm （ Such as MillerRabin） Yes n Perform onetime prime detection , If n If it fails, the random number is regenerated , If n If the test passes, repeat the test for many times , If both pass, then n Select as ideal prime .
give an example ：e=3 n=7,e and n It's reciprocal . Can find d=5 , send e*d1 By n to be divisible by （3*51 By 7 to be divisible by ）.
5 RSA Common attack algorithms
5.1 Modulus decomposition
5.2 Direct decomposition N
windows Platform RSATool
Online website http://factordb.comhttp://factordb.com/
5.3 greatest common divisor
5.4 Low encryption index attack （ Low encryption index broadcast attack ）
5.5 Low decryption index attack
5.6 Common mode attack
5.7
There is a blog that is easy to read .
6 It is known that x.509 certificate , Steps to obtain the private key
6.1 from x.509 Extract public key information from .
The format of public key information is ：
BEGIN PUBLIC KEY
MIIB*********************************************
END PUBLIC KEY
For the method of obtaining, refer to the following blog 3.1 chapter
6.2 Extract... From the public key file 16 Base number N,E
Use the online toolbox Website TheX Online toolbox Base64 decode AES RAS decode encryption Base64,DES,AES,RSA,BASE16,Hex Such as conventional encryption / Decryption tools . Original data inspection technology, fully automatic recognition results . Provide accurate handling suggestions .https://thex.cn/
Remove BEGIN PUBLIC KEY and END PUBLIC KEY Paste the public key after two lines , You can get N,e Of base64 Code file . Then through the counter base64f Method can obtain 16 It's binary N and e.
6.3 utilize N and e Calculate private key
Now we have N and e, Calculate the private key d There is already a theoretical possibility . The following code is the code that can calculate the private key . If N The length of the shorter , The results can be calculated in a short time . If N Longer than 512, Then our method can only help you learn .
Compute private key with known public key python Code
import random
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
def getpq(n, e, d):
p = 1
q = 1
while p == 1 and q == 1:
k = d * e  1
g = random.randint(0, n)
while p == 1 and q == 1 and k % 2 == 0:
k /= 2
y = pow(g, int(k), n)
if y != 1 and gcd(y  1, n) > 1:
p = gcd(y  1, n)
q = n / p
return p, q
# Decomposition modulus n
def rsa_moder(n):
base = 2
while base < n:
if n % base == 0:
return base, n // base
base += 1
# Find Euler functions f(n)
def rsa_get_euler(prime1, prime2):
return (prime1  1) * (prime2  1)
# Private key
def rsa_get_key(e, euler):
k = 1
while True:
if (((euler * k) + 1) % e) == 0:
return (euler * k + 1) // e
k += 1
# according to n,e Calculation d( Or according to n,d Calculation e)
def get_rsa_e_d(n, e=None, d=None):
if e is None and d is None:
return
arg = e
if arg is None:
arg = d
primes = rsa_moder(n)
p = primes[0]
q = primes[1]
d = rsa_get_key(arg, rsa_get_euler(p, q))
return d
def main():
# n = 25777
# e = 3
# print("input n is ",n)
# print("input e is ",e)
# d = get_rsa_e_d(n, e, None)
# print("result: d is ",d)
n = 0xBB012883****( length 2048bit,16 Hexadecimal length 256)
e = 0x10001
print("input n is ",n)
print("input e is ",e)
d = get_rsa_e_d(n, e, None)
print("result: d is ",d)
p, q = getpq(n, e, d)
print("result: p = ", p)
print("result: q = ", int(q))
if __name__ == '__main__':
main()
We test the correctness of the code with the public key information of the small module .
D:\Users\PycharmProjects\pythonProject\venv\Scripts\python.exe D:/Users/PycharmProjects/pythonProject/main.py
input n is 25777
input e is 3
result: d is 16971
result: p = 149
result: q = 173
Process finished with exit code 0
版权声明
本文为[Xiao Xiangzi]所创，转载请带上原文链接，感谢
https://chowdera.com/2021/12/202112122244406563.html
边栏推荐
 The world is always hostile to good people.
 Re regular matching findall (. +?) Match any content that conforms to a certain format (regular matching catch bullet screen)
 Android中的羊角符，面試看這個就够了
 數據分析八大模型：OGSM模型
 La corne d'agneau d'Android, c'est assez pour l'interview
 Huit modèles d'analyse des données: modèle ogsm
 Exemple d'application de linq
 Utilisez S7. Net communication library
 Écrire La Bibliothèque de communication Modbus TCP
 Lire le profil INI
猜你喜欢

Utilisez S7. Net read Siemens 1500plc

Halcon joint C # Programming Experiment

Utiliser nmodbus4 pour lire les données à la fois RTU et TCP

Tiktok Data Analysis options Platform  tichoo Data

MySQL review: create tables, MySQL data types, primary key constraints, primary key

Linear Algebra: matrix review

Review of Linear Algebra: determinant

The digital RMB crossborder payment test has been continuously promoted, and mainland residents can also shop in Hong Kong in the future

Thesis classification and writing basis

YC Framework version update: v1.0 zero point two
随机推荐
 Analyse des données tichoo
 Tiktok data analysis platform
 Partage de l'industrie  tichoo Data to attend 2022 Overseas Short video Industry Summit
 [ticoo Information Station] tiktok and Cross  Border E  commerce Weekly Report
 Options d'analyse des données ticoo {infostation}
 Partage de l'industrie  Lu Shidong, PDG de tichoo Data Outlook Global Video e  commerce future Blueprint
 [ticoo Information Station]
 Noël Black Five
 YC Framework version update: v1.0 zero point two
 Lucene分词器
 Gbase 8A slow SQL optimization case
 微服务系列聊聊微服务治理中的一些感悟
 线程池的经典应用场景
 [web security from getting started to giving up] 07_ Insecure file download and upload vulnerability
 如何落地一款重试组件
 一起聊聊设计原则
 大话Redis系列深入探讨多路复用（上）
 大话Redis系列实战案例总结（下）
 大话Redis系列实战案例总结（上）
 JVM系列  G1与低延迟垃圾收集器
 JVM系列  深入剖析垃圾收集器
 JVM系列内存回收
 JVM系列对象内存分配技术分析
 JVM系列虚拟机的内存管理
 系统性能瓶颈排查技术总结
 使用redis的scan指令详解
 实战分布式id发号器
 分布式事务之超详细的Seata实践记录
 TCP time_wait
 IP数据报头部
 最大基环内向树
 MySQL实战45讲 学习笔记（七）
 MySQL实战45讲 学习笔记（六）
 Android从零开始搭建MVVM架构（1）(1)，kotlin匿名函数
 Android事件分发机制五：面试官你坐啊，安卓上机面试题
 There will be two different stages between the breakthrough of science and technology and its real transformation into an inclusive technology
 [leetcode] force deduction 200 Number of islands
 HashShuffleManager
 Altium Designer
 Android construit l'architecture mvvm à partir de zéro (1) (1), fonction anonyme kotlin