这种体制思想是简单的，但是，如何找到一个适合的算法来实现这个系统却是个真正困扰密码学家们的难题，因为既然Pk和SK是一对存在着相互关系的密钥，那么从其中一个推导出另一个就是很有可能的，假如敌手Oscar能够从PK推导出SK，那么这个系统就不再安全了。因此如何找到一个合适的算法生成合适的Pk和SK，并且使得从PK不可能推导出SK，正是迫切需要密码学家们解决的一道难题。这个难题甚至使得公钥密码系统的发展停滞了很长一段时间。
为了解决这个问题，密码学家们考虑了数学上的陷门单向函数，下面，我们能够给出他的非正式定义：
Alice的公开加密函数应该是容易计算的，而计算其逆函数（即解密函数）应该是困难的（对于除Alice以外的人）。许多形式为Y=f（x）的函数，对于给定的自变量x值，很容易计算出函数Y的值；而由给定的Y值，在很多情况下依照函数关系f (x)计算x值十分困难。这样容易计算但难于求逆的函数，通常称为单向函数。在加密过程中，我们希望加密函数E为一个单项的单射函数，以便能够解密。虽然现在还没有一个函数能被证实是单向的，但是有很多单射函数被认为是单向的。
例如，有如下一个函数被认为是单向的，假定n为两个大素数p和q的乘积，b为一个正整数，那么定义f ：
f (x )= x b mod n
(假如gcd（b,φ（n））=1，那么事实上这就是我们以下要说的RSA加密函数)
假如我们要构造一个公钥密码体制，仅给出一个单向的单射函数是不够的。从Alice的观点来看，并无需E是单向的，因为他需要用有效的方式解密所收到的信息。因此，Alice应该拥有一个陷门，其中包含容易求出E的您函数的秘密信息。也就是说，Alice能够有效解密，因为他有额外的秘密知识，即SK，能够提供给您解密函数D。因此，我们称一个函数为一个陷门单向函数，假如他是个单向函数，并在具备特定陷门的知识后容易求出其逆。
考虑上面的函数 f (x) = xb mod n 。我们能够知道其逆函数f -1有类似的形式 f (x ) = xa mod n，对于合适的取值 a。陷门就是利用 n的因子分解，有效的算出正确的指数a（对于给定的b）。
为方便起见，我们把特定的某类陷门单向函数计为Ғ。那么随机选取一个函数f 属于Ғ，作为公开加密函数；其逆函数f -1是秘密解密函数。那么公钥密码体制就能够实现了。
根据以上关于陷门单向函数的思想,学者们提出了许多种公钥加密的方法，他们的安全性都是基于复杂的数学难题。根据所基于的数学难题，至少有以下三类系统现在被认为是安全和有效的：大整数因子分解系统(代表性的有RSA)、椭园曲线离散对数系统(ECC)和离散对数系统 (代表性的有DSA)。
§3 RSA算法
3.1 简介
当前最著名、应用最广泛的公钥系统RSA是在1978年，由美国麻省理工学院(MIT)的Rivest、Shamir和Adleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。他是个基于数论的非对称(公开钥)密码体制，是一种分组密码体制。其名称来自于三个发明者的姓名首字母。 他的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此能够确保RSA算法的安全性。RSA系统是公钥系统的最具备典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。
RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此他为公用网络上信息的加密和鉴别提供了一种基本的方法。他通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文档发送给个人，个人就能够用私钥解密接受。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。
该算法基于下面的两个事实,这些事实确保了RSA算法的安全有效性：
1) 已有确定一个数是不是质数的快速算法；
2) 尚未找到确定一个合数的质因子的快速算法。
3.2 工作原理
1) 任意选取两个不同的大质数p和q，计算乘积r=p*q；
2) 任意选取一个大整数e，e和(p-1)*(q-1)互质，整数e用做加密密钥。注意：e的选取是很容易的，例如，任何大于p和q的质数都可用。
3) 确定解密密钥d： d * e = 1 modulo（p - 1）*（q - 1） 根据e、p和q能够容易地计算出d。
4) 公开整数r和e，但是不公开d；
5) 将明文P (假设P是个小于r的整数)加密为密文C，计算方法为：
C = Pe modulo r
6) 将密文C解密为明文P，计算方法为：
P = Cd modulo r
然而只根据r和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。
3.3 简单实例
为了说明该算法的工作过程,我们下面给出一个简单例子,显然我们在这只能取很小的数字，但是如上所述，为了确保安全，在实际应用上我们所用的数字要大的多得多。
例：选取p=3, q=5，则r=15，（p-1）*（q-1）=8。选取e=11（大于p和q的质数），通过d * 11 = 1 modulo 8，计算出d =3。
假定明文为整数13。则密文C为
C = Pe modulo r
= 1311 modulo 15
= 1,792,160,394,037 modulo 15
= 7
复原明文P为：
P = Cd modulo r
= 73 modulo 15
= 343 modulo 15
= 13
因为e和d互逆，公开密钥加密方法也允许采用这样的方式对加密信息进行"签名"，以便接收方能确定签名不是伪造的。
假设A和B希望通过公开密钥加密方法进行数据传输，A和B分别公开加密算法和相应的密钥，但不公开解密算法和相应的密钥。A和B的加密算法分别是ECA和ECB，解密算法分别是DCA和DCB，ECA和DCA互逆，ECB和DCB互逆。 若A要向B发送明文P，不是简单地发送ECB（P），而是先对P施以其解密算法DCA，再用加密算法ECB对结果加密后发送出去。
密文C为：
C = ECB（DCA（P））
B收到C后，先后施以其解密算法DCB和加密算法ECA，得到明文P：
ECA（DCB（C））
= ECA（DCB（ECB（DCA（P））））
= ECA（DCA（P）） /*DCB和ECB相互抵消*/
= P /*DCB和ECB相互抵消*/
这样B就确定报文确实是从A发出的，因为只有当加密过程利用了DCA算法，用ECA才能获得P，只有A才知道DCA算法，没 有人，即使是B也不能伪造A的签名。
文章整理：西部数码--专业提供域名注册、虚拟主机服务
http://www.west263.com
以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!
