# Shor-CrackRSA

**Repository Path**: xpeter/Shor-CrackRSA

## Basic Information

- **Project Name**: Shor-CrackRSA
- **Description**: 利用Shor算法，在IBM-Q上16位量子计算机上破解RSA公钥体系的示例
- **Primary Language**: Python
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 9
- **Forks**: 4
- **Created**: 2020-06-27
- **Last Updated**: 2024-03-07

## Categories & Tags

**Categories**: quantum

**Tags**: None

## README

# Shor-CrackRSA

#### 介绍
利用Shor算法，在IBM-Q上16位量子计算机上破解RSA公钥体系的示例
效果：
![输入图片说明](http://www.xpeter.net:88/yyh/RSA.gif "破解RSA")


#### 如何启动？
1、建立一个Python3的执行环境

2、$ pip3 install -r requirements.txt

3、直接执行test.py,或在jupyter notebook中执行Breaking_RSA.ipynb


$ python test.py

或

$ jupyter notebook Breaking_RSA.ipynb

4、输入因子位数4，输入明文（任意长度），获得密文，用私钥解密，连接IBM-Q用shor算法解密
注意：由于量子计算机仅提供16位的，因此，因子位数最多16的平方根位，但不代表RSA是4位，因为RSA是两个因子乘积的二进制数，大约最多能支持RSA-17。对于更高位数的RSA，比如RSA-2048需要大概617个十进制数，分解的因子大小约为309位，大约需要9万位的量子计算机做一次运算，但如果多次运算或采用分布式量子计算机（美国能源部橡树岭国家实验室（ORNL）的拆分光束分布式方案）可以在低位量子计算机上实现对现有公钥体系的威胁成为现实。

早在 1994 年，Peter Shor就发明了一个量子算法（Shor算法），在整数的质因数分解上，能实现的时间复杂度降低到O(log N)
详细了解见本源量子详细教程：


[彻底搞清楚Shor算法](https://www.bilibili.com/video/BV1a4411M7cU)