5-1RSA密码中的素数判定

RSA密码中的素数判定潘森杉计算机科学与通信工程学院，江苏大学密码学能说出公钥密码的优缺点

认识和遵循密码方案参数设置规则能够使用Miller-Rabin判定大素数目录公钥密码的优缺点问题：为什么要用公钥密码来保护信息安全？目标：识别适用场景和意义公钥密码的优缺点

小艾小戴小蔡小鲍小张优点：1.安全密钥分发2.密钥管理开销小3.信息可验证私钥公钥公钥公钥公钥公开信道公开信道公开信道公开信道公开信道缺点：加解密速度比对称密码慢密钥长度较长公钥认证问题RSA核心应用场景

电子商务：HTTPS协议加密​应用方式：网站部署SSL/TLS证书，握手阶段用RSA交换会话密钥​实例：淘宝、京东等电商平台，用户输入的银行卡号、支付密码，通过RSA加密后传输，防止被窃取​关键价值：避免支付信息在传输中被篡改或泄露​数字签名：身份验证与防篡改​应用1：软件分发（如Windows系统、Adobe软件）​开发者用私钥对软件哈希值签名，用户用公钥验证——确认软件未被植入病毒​应用2：电子合同（如法大大、e签宝平台）​签约方用私钥签名，合同接收方用公钥验证——确保合同完整性、不可否认性​实例：企业远程签约劳动合同，通过RSA数字签名替代纸质盖章​VPN通信：企业远程安全访问​应用方式：企业搭建VPN时，用RSA加密VPN隧道内的数据​场景：员工居家办公访问公司内网（如财务系统、客户数据库）​实例：华为VPN、CiscoVPN设备，均集成RSA加密，防止内网数据被外部拦截​RSA算法的工作流程密钥生成加密解密玩具RSA算法加解密目标：能够演示如何配置并使用RSA算法加解密一串英文文本的过程

玩具RSA算法加解密(Python)#生成密钥对p=61q=53n=p*qphi_n=(p-1)*(q-1)e=17d=0while(d*e)%phi_n!=1:d+=1print(f"PublicKey(e,n):({e},{n})")print(f"PrivateKey(d,n):({d},{n})")#加密数据m=65#对应字母'A'c=(m**e)%nprint(f"EncryptedMessage:{c}")#解密数据decrypted_m=(c**d)%nprint(f"DecryptedMessage:{decrypted_m}")输出：PublicKey(e,n):(17,3233)PrivateKey(d,n):(2753,3233)EncryptedMessage:2790DecryptedMessage:65只有私钥(2753,3233)的拥有者才能解密方案建模——RSA算法的详细工作流程

RSA算法的安全性问题：密钥生成，即如何基于数学难题打造一把安全锁和对应的钥匙目标：认识到密码方案的参数设置对安全性的影响，并能够在遵循方案的设计准则下正确使用密码方案公钥n需要如何设置？#生成密钥对p=61q=53n=p*qphi_n=(p-1)*(q-1)e=17d=0while(d*e)%phi_n!=1:d+=1print(f"PublicKey(e,n):({e},{n})")print(f"PrivateKey(d,n):({d},{n})")问题：任何有p、q的人都能计算出私钥dRSA因子分解攻击2018AFCTF脆弱原因：

7983218175...43<623>

=

3133337

·

2547832606...39<617>步骤1）工具分解模数n得到p、q，例如2）通过欧拉定理、p、q求e的模逆元得到d3）解密并转换成字符串制作RSA锁壳n的设计图——素数问题：锁的安全级别需要设置多高才行？为什么？制作RSA锁壳的设计图——素数密钥n长度(bits)所需计算操作数(估算)破解所需时间(用现有硬件估算)1024~2⁸⁰已不再安全，已被专业机构淘汰2048

(当前标准)~2¹¹²即使用最强大的超级计算机，也需要数百万年3072~2¹²⁸比2048位安全级别高得多4096~2¹⁴⁴在可预见的未来（甚至量子计算机前）绝对安全指挥AI深挖专业知识：为什么n为2048时，破解RSA的计算操作约等于2¹¹²？动手任务1：请AI寻找大素数批判思考：如何判断AI没有忽悠你？打造“锁壳”：公开的模数n=p*q动手任务2：请AI计算大数乘法AI响应示例：(会输出一个更长的数字N)思考如何编程实现大数相乘拿到锁的人能恢复出设计图纸吗？为什么？核心原理：RSA的安全性基于一个数学事实：将两个大素数相乘很容易，但将其乘积分解还原为原来的两个素数极其困难。拓展：借助AI类比不同公钥密码方案的联系核心数学难题大整数质因数分解

n=p*q椭圆曲线离散对数问题(ECDLP)

Q=k*P格上最短向量问题(SVP)/差错学习(LWE)

b=A*s+e打造“锁”(公钥)公开乘积

n

和指数

e公开曲线点

P

和乘积点

Q=k*P公开矩阵

A

和结果向量

b=A*s+e打磨“钥匙”(私钥)保密质因数

p

和

q，或模逆元

d保密倍数

k保密秘密向量

s

和小误差

e“正向容易”计算大数乘法

p*q

很容易计算标量乘法

k*P

很容易计算矩阵乘法

A*s+e

很容易“逆向困难”从

n

分解出

p

和

q

极难从

P

和

Q

求出

k

极难从

A

和

b

求出

s

和

e

极难“陷门”作用知道

p

和

q

就能轻松计算

d知道

k

就能轻松完成解密运算知道

s

和

e

就能轻松纠正误差完成解密优势理解直观，应用广泛效率高：相同安全强度下，密钥比RSA短得多抗量子计算：被认为能抵抗量子计算机的攻击生成大素数的步骤制作RSA锁壳的设计图——素数素性判定方法平方差检验

检测合数的方法Fermat定理如果p是素数，那么对于任意整数a，有a^(p-1)≡1(modp)。思考：如何运用该定理检测合数？122≡22(mod35)，12≢±2(mod35)，35是一个合数，gcd(12-2,35)=5是35的一个非平凡因子例素性判定与因子分解的难度不一样复杂度为O(log(n))，比因子分解容易

例

定义Fermat定理素性判定的缺陷Fermat定理不能100%确定一个数是素数

最小的Fermat伪素数341，2^340mod  341=1但341=11×31。例Miller-Rabin素数判定步骤算法效率

概述概率性算法基于费马小定理和二次探测定理，通过多次随机测试来提高判定结果的准确性。030201分解

n−1随机选择基底a测试基底

a结果判定

Miller-Rabin素数判定测试

n=25

是否为素数误判原因算法中使用的a是随机的改进方法Miller-Rabin测试中的误判问题*增加测试的轮数*选择更大的随机数种子0102确定性算法AKS素性判定，多项式时间03定理：若a是随机选取的，则Miller-Rabin判定将合数当成素数的概率不超过1/4。AI类比不同素数测试的区别：

性能上的微小代价，换来了安全性的巨大提升特性费马素数测试米勒-拉宾素数测试理论基础费马小定理费马小定理+二次探测定理确定性概率性概率性错误类型合数被误判为素数（伪素数）合数被误判为素数（强伪素数）错误率（单次随机测试）较高。存在大量的卡迈克尔数，能通过所有基数的费马测试。极低。对任意合数，至少75%的基数会证明其是合数。实际错误率不可接受。无法可靠地排除卡迈克尔数。可接受。经过少量迭代（如5-10次），误判概率可忽略不计（如<1e-60）。计算步骤模幂运算：an−1 mod nan−1modn模幂运算+零到多次的平方模运算单次测试计算量略低略高（因为额外的平方检验步骤）实际性能差异差异极小。额外的平方检验在计算总量中占比很小，因为主要开销都在大数模幂运算上。安全性不安全，已被淘汰。无法有效检测出卡迈克尔数，攻击者可能利用此构造易分解的n。安全，行业标准。没有已知的类似卡迈克尔数的“漏洞”。主要缺陷卡迈克尔数（如561,1105,1729...）无已知重大缺陷

Miller-Rabin素数判定测试

n=561

是否为素数?费马测试仅在基数a是561的因子时才能成功RSA因子分解攻击

n=20499421483319837632829005665244953604816631094131482091599739242452461959670789327098587429656441009883765163931516947567316643569963621519243386576155541991650610105070387440479691299670503655019032377026089584152047162143622592606512093871068907193787013919967475201572411584456318069752118161110853731611597336602111728937901380008855876406951363681839727114631417566905375167058609392654378267988132283758536576123045237315624774544667706040426027925497245266590365080287798629911056879889563806490213919247917120199512548392006107613124668838850719777385822083736801474373012496703900585089950184532462833403107e=65537c=2003257190833455651870699635062835376285793209037393368140088894431278594766161669409470119586285076191009716855867587562721505277326083265989337412792759822723602653089715225216720180093903010421453632730491243080976026442851203293732830260859217604018454748342371157117174405596814865736665507478813983254321218492419171597619190519870117069394125209789541614637235135539220531691330467202335066455417042235339275117764090541622850242978171441807792686826412429353934993161912348509850100524980682989627023983568208281803533336450699582362101086797982066284771