里维斯特、沙米尔和艾德莱曼
当迪菲和赫尔曼提出“公钥密码系统”时，人们并不知道如何利用这项理论设计“公钥”和“私钥”。两年后，才由美国马萨诸塞理工学院的三位研究员里维斯特、沙米尔和艾德莱曼联名提出了第一个实用的公钥密码方案——后被称为“RSA方法”。这是一种用来产生密钥的方法，由它形成的密码几乎能够抵御一切密码攻击。如今，该方法已在互联网上广泛使用。RSA方法依赖于初等数论中一条著名的定理：费马小定理，即设p是任意大于2的素数，a是任意的与p互素的非零整数，则必然有ap-1≡1（mod p），[一般地，m≡n（mod k）表示m-n被k（k≠0）整除]其中mod p就表示被p除后的余数。
用RSA方法产生私钥和公钥的过程大致如下：首先是随机寻找两个大素数p和q，计算n=pq，ϕ（n）=（p-1）（q-1）；然后找一个与ϕ（n）互素的合适的正整数e，并用欧几里得辗转相除法找到另一个正整数d，使得ed≡1（modϕ（n））；最后把整数对（e, n）作为“公钥”放在公共网络上，（d，ϕ（n））则是“私钥”，需要保密。
如果网络用户甲要给乙发送一段需要保密的文本信息M（不妨假设M是一个正整数且小于n），则甲应如此操作：找到乙的公钥（e, n），并计算
然后将
发送给乙。乙收到甲发来的
后，就用自己的私钥计算
用费马小定理可以证明：
于是得到原文M。外人并不知道乙的私钥，所以不能获取原文。
通过类似的操作，用RSA方法也能够容易地实现数字签名。
RSA方法之所以可行，是基于以下关于大整数运算的若干事实：第一，可以运用计算机实现两个大整数的快速相乘；计算两个m位数相乘所需要的基本运算次数约为mlgm，所以，即使是几千位数字的相乘也可以很快完成；第二，存在寻找大素数的快速计算方法，数论知识告诉我们，在不大于n的正整数中，平均存在着n/lnn个素数，所以运用计算机可以很快找到所需素数；第三，不存在分解一个大整数的有效方法。
任何人企图破解密文就必须知道私钥（d，ϕ（n））中任意一个值；而要利用公钥（e, n）来算出d或ϕ（n），就必须分解n。所以，谁要是能找到分解大整数的有效方法，就能攻破RSA密码，整个互联网也因此会立刻崩溃。
所幸的是，我们已经知道分解整数属于NP问题。对于NP问题是否存在有效算法，这是一个世界著名难题，而且答案很可能是否定的。所以，互联网目前还很安全。（善平）
【微问题】你能自己构造一套简单的密码系统吗？
【关键词】公钥密码系统 RSA方法
- 北京猿人是不是现代中国人的祖先
- 北京鸭为什么特别肥?
- 北冰洋上的冰会完全消失吗
- 北冰洋冰盖会消失吗?
- 北冰洋是怎样变咸的
- 北冰洋航线什么时候能够开通
- 北斗七星天文学上称之为什么星座
- 北方人为什么普遍都那么高?
- 北极为什么没有企鹅?
- 北极为什么没有企鹅
- 北极和南极哪个地方更冷？
- 北极地区因人造化学制剂导致男女比例失衡
- 北极夏天的太阳为什么总不落山
- 北极星一直都是勾陈一吗？
- 北极星在哪？
- 北极最大的资源是什么
- 北极熊为什么不怕冷?
- 北极熊为什么没有固定的睡眠姿势
- 北极熊为何变“苗条"了?
- 北极独角鲸生存面临人类威胁
- 北欧中世纪的维京人都是海盗吗
- 北燕为什么南飞?
- 北理工“新鹰"何以在国际顶级无人机大赛夺魁
- 北祁连断褶
- 北美之外还有哪些大型的恐龙行迹？