RSA公开密钥体制及其主要数学基础

1、RSA公开密钥体制及其主要数学基础江西省上犹县教师进修学校 (341200) 舒昌勇在密码学发展的历史上，1976年是一个值得纪念的年份这一年，美国斯坦福大学年轻的数学家狄菲（Diffie）和计算机专家海尔曼(Hellman)联名发表了密码学的新方向一文，开创了现代密码学的新领域公开密钥体制（简称公钥体制）30年来，公钥体制获得了巨大的发展，它不仅消解了传统的秘密密钥体制存在的一些困难，而且解决了信息安全的一些问题，推动了包括电子商务在内的一大批网络应用的深入和发展1 公开密钥体制的提出11传统密钥体制遭遇的困难（1）用户的增加使大量密钥管理成为严重问题在传统的秘密密钥保密通信中，每一对发方和

2、收方都要拥有一对密钥：加密密钥E和解密密钥D发方把要发送的明文信息x用加密密钥加密成密文y发送；收方收到密文y后用解密密钥D将之解密为明文x所以从数学上说，加密密钥E和解密密钥D是互逆的，经过它们的共同作用，明文信息x经过加密和解密仍旧变换为明文信息：D（E(x)）=E（D(x)）= x所以，只要知道E、D中的任何一个就能很容易地求出另一个因而密钥E、D都要保密从20世纪60年代起，由于因特网络为通信提供的便利，保密通信的应用领域不断扩大，用户大量增加假设有2000个用户彼此进行保密通信，因每2个用户就需一对密钥，整个通信系统一共需要C 22000=(2000×1999)÷

3、2=1999000对密钥，每个用户要保管他和其余1999个用户间的1999对密钥，这让我们不难理解巨大的密钥量给密钥管理、分配和为了确保信息安全而对密钥定期更换方面带来的困难 （2）数字签名和身份认证的问题亟待解决在通常的书信和文件中，人们常常用签名、印章或指纹来表明自己的身份，收方也凭此来确认信、文是否来自发方，在数字通信中同样存在这类问题但发方如何在信息上签名？收方如何确认发方的身份？如何辨认信息是否系伪造或被修改？这些问题因与信息的安全密切相关都亟待解决12 大整数因子分解的无奈根据算术基本定理：任何大于1的整数总可以分解成素因数乘积的形式，并且，如果不计分解式中素因数的次序，这种分解式

4、是唯一的这个定理在理论上十分漂亮，但操作起来对大整数却非易事甚至实际并不可能表1列出了用现代最快速的分解算法，在大型计算机上分解一个大整数所需的时间这让我们看到大整 表1 整数的位数操作次数所需时间501.4×1010 3.9小时759.0×1012 104天1002.3×1015 74年2001.2×1023 3.8×109年3001.3×1029 4.9×1015年5001.3×10394.2×1017亿年数分解在目前是一个非常困难的问题让人未曾想到的是，正是这种困难为一种新的密钥体制的“核心部件”单

5、向函数的构造提供了重要的机会13 公开密钥思想的提出（1）单向函数1976年，狄菲和海尔曼在密码学的新方向一文中，提出采用“单向函数”来设计公钥体制的思路所谓“单向函数”，是指加密函数E和解密函数D的运算都容易实现，但由E求其逆运算D却非常困难这样，即使把加密函数E和具体的加密与解密的算法过程都公开，如果不知道解密函数D，把密文解密成明文的计算也无法实现（2）公钥体制的基本思想在公钥体制中，密钥管理中心为每个用户设计一对密钥加密密钥和解密密钥，加密密钥可以公开，称为公钥，解密密钥由用户自己秘密保管，称为私钥每个用户与其它任何一个用户的密钥都不相同，在他拥有的一对密钥中，公钥与私钥也不相同，而且

6、由公钥推导出私钥也绝不可行但它们又密切联系着：用公钥加密的信息只能用与之配对的私钥才能解密，用私钥加密的信息也只能用与之配对的公钥才能解密14 公钥体制的工作原理设某公司的n个用户要进行保密通信，密钥管理中心分别为每个用户Ai(i=1，2，n)设计一对密钥（Ei，Di），将公钥Ei汇编成公钥簿供所有用户查找，将私钥Di秘密提供给用户Ai使用并由Ai秘密保管当某用户要发信息x给用户Ai时，先在公钥簿上查找到Ai的公钥Ei，用它将明文信息x加密成密文信息y=Ei (x)，然后通过公开信道发给AiAi收到密文信息y后，用私钥Di作用于y ：Di (y)= Di（Ei (x)）= x由于用Ai的公钥E

7、i加密的密文信息，只有用Ai的私钥Di才能解密成明文信息，所以即使密文信息被他人截获，也无法解密成明文，因而保证了公钥体制通信的安全性在前述2000个用户秘密通信的问题中，假如采用公钥体制，由于1个用户只需要拥有1对密钥，所以整个通信系统只需2000个密钥对，每个用户也需记忆与保管属于自己的1个私钥就行，与前述相应的1999000对和1999对相比，分别减少了近1000倍和近2000倍！2 RSA公钥体制的基本原理其实，由狄菲和海尔曼提出的公钥体制只是一种思想，他们开创性的论文引进了密码学的一种新方法，但同时也给密码学专家提出了一个挑战性的问题：能否设计一个满足公钥体制要求的加密与解密的算法？

8、1977年，美国麻省理工学院的里弗斯特(Rivest)，沙米尔(Shamir)、阿德勒曼(Adleman)联合设计出著名的RSA公钥体制这种以他们姓氏的首字母命名的密钥体制的主要数学基础是RSA定理，该定理牵涉较多的数论知识，我们先来做些准备21 RSA定理相关的数论知识（1）一个大于1的整数p，如果除1和它本身外没有其它正整数因数，称p是素数（2）若整数a、b的最大公因数为1（记为（a,b）=1），称a、b互素（3）设n为正整数，a和b为整数，如果a和b被n除后的余数相同，称a和b模n同余记为ab(modn)称此式为同余式n能整除a一般可用同余式 a0(modn)表示两个整数a、b模n同余的

9、等价说法有：a和b被n除余数相同；a和b在模n的同一个剩余类中；ab能被n整除；存在整数s，使得a=sn+b（4）同余式有一些运算性质，比如： 若ab(modn)，c=d(modn)，则acbd(modn) (同余式的乘法性质)特别地，有ka=kb(modn)，k为任意整数 若ab(modn)，d是a、b、n的公因数，则 (mod) 若abac(modn)，且a与n互素，则bc(modn) (同余式的消去律)（5）设n为正整数，则任何一个整数被n除，余数必为0，1，2，n-1中的某一个把整数集中被n除余数同为0，1，2，n-1的数分别归为一类，记为0，1，2，n-1，这样就按模n是否同余把整数

10、集分成n类，其中每一类都称为模n的一个剩余类显然，每个整数必属于上述n类中的一类，被n除余数不同的数必属于上述的不同类中若a0，a1，a2，an-1分别取自上述n类的不同类中，称a0，a1，a2，an-1为模n的一个完全剩余系，该剩余系中的数两两模n不同余（6）含有未知量的同余式称为同余方程一次同余方程是最简单的一种，其一般形式为axb(modn)若a，n的最大公因数d能整除b，则axb(modn)有解，且恰有d个解若a，n的最大公因数d不能整除b，则axb(modn)无解例如一次同余方程7 x1（mod5），因为（7，5）=1，1整除b =1，所以同余方程有1个解求解过程为：7x1（mod5

11、）6111621（mod5），因7与5互素，由同余的消去律，得其解为：x3(mod5) 一般地，解同余方程的步骤为：判断解的情况；当同余方程的a、b、n有公因数时，约去公因数化简方程；利用同余的定义和消去律求方程的解（7）费马小定理：设任意整数a与素数p互素，则a p-11(modp) 证明：由a与素数p互素，知p不是a的素因数又因为p也不是1，2，3，p1的素因数，所以a乘以此数列各项所得新数列a，2a，3a， ，(p1)a各项都不能被p整除从而a，2a，3a， ，(p1)a中的每一项只能和数列1，2，3，p1中的一项模p同余又由于a，2a，3a， ，(p1)a中的任意两项都不能模p同余（事

12、实上，如果存在不同的两项ra与sa（不妨设0rsp）模p同余，即sara(modp)，因a与p互素，据同余式的消去律可得sr(modp)，与假设rs矛盾），所以a，2a，3a， ，(p1)a中恰有一项和1，2，3，p1中的1同余，恰有一项和1，2，3，p1中的2同余，恰有一项和1，2，3，p1中的p1同余，从而可以建立p1个同余式将这p1个同余式相乘得：a·2a·3a (p1)a1·2·3p1(modp) 因1·2·3p1与p互素，由同余的消去律得a p-11(modp)22 RSA定理及其证明定理 设p、q是不同的素数，n=pq，记

13、(n)=（p1）（q1），如果e、d是与(n)互素的两个正整数，并满足ed1(mod(n)，则对于每个整数 x，都有x e dx(modn)分析 由同余定义的等价表述，只要证n是x e dx的因数但n=pq，且p、q都是素数，所以只要证p、q分别是x e dx的因数，即只要证对于每个x，都有x e dx(modp) x e dx(modq)证明 式只要证x e dx0(modp) 如果p是x的因数，则上式显然成立；如果p不是x的因数，即p与 x互素，由题设ed1(mod(n)，知(n)是 ed1的因数，故存在整数k使得 ed1=(n) k=（p1）（q1）k，从而ed=1+（p1）（q1）k，

14、x e d =x1+（p1）（q1）k =x·（x p1）（q1） k，因p与x互素，由费马小定理a p-11(modp)，可得x e dx·（1）（q1）kx(modp) 同理可证式也成立因此有：x e dx(modn) 23 RSA公钥体制的原理以下RSA公钥体制实施的步骤，会帮我们理解它的基本原理：（1）取两个超过100位的大整数p和q，求出n=pq和(n) =（p1）（q1）的值（2）选一个与(n) 互素的正整数e，解同余方程ed1(mod (n)，得到解d，则e,d是可供一个用户使用的密钥对其中e为公钥，d为私钥（3）构造两个定义域为0，1，2，n1的函数：E(x

15、)= x e (mod n) 为加密函数，D(x)= x d (mod n)为解密函数（4）根据RSA定理，D(E(x)= D(x e)=(x e) d= x e d x(mod n),即在D(x)和E(x)的作用下，经加密和解密后，明文信息x变换为密文y后又恢复为明文x所以E(x) 和D(x)是互逆的（5）把供某用户使用的私钥d交该用户，并将其公钥e和n公开，(n)则由密钥制作者秘密保管（6）别的用户要与该用户秘密通信时，先将明文信息x用该用户的公钥e建立的加密函数E(x)加密，得密文y = E(x)x e (modn)，该用户收到密文y后，用自己的私钥d建立解密函数D(x)解密，得明文x=

16、D(y)y d(modn)(x e) dx e d x(modn)为什么这里构建的加密函数E（x）xe (mod n)是单向函数？因为n是素因数p与q很大的整数，所以即使知道n，也极难求出p和q，从而也无法得到(n) 因此在能查到公钥e的情况下，也不能建立同余方程ed1（mod(n)）,不能得到私钥d故E（x）xe(mod n)为单向函数24 用RSA公钥体制进行数字签名和身份认证RSA公钥体制提出后，人们立刻发现也能用它来解决数字签名和身份认证问题当甲与乙通信时，把明文信息x先用自己的解密函数对它签名：D甲(x)=y如果信息内容无需保密，甲就可将经他签名的信息y发给乙乙收到信息就从公钥薄上查

17、到甲的公钥得到加密函数作用于y ：E甲（y）= E甲（D甲（x）=x，得到明文信息x，从而确认信息x是来自甲如果信息内容需要保密，甲在签名后又在公钥簿上查到乙的公钥得到加密函数，用它对已经签名的信息y加密：E乙(y)= z，然后把z发给乙乙收到z后，先用自己的解密函数作用于z：D乙(z)=D乙(E乙(y)= y ，再从公钥簿上查到甲的公钥得到加密函数作用于y ，E甲(y)= E甲（D甲(x)）=x，得到并确认来自甲的明文信息x3 RSA公钥体制的实施举例RSA公钥体制中，单向函数的构造基于大整数n因数分解的困难，因而 n的两个因数p与q都应取大素数为便于理解，我们选取两个较小的素数来说明该体制

18、的实施例 给定两个素数p=13和q=17（1）试为用户A1和A2设计RSA公开密钥；（2）用户A1要把信息 x =3加密后发送给用户A2，试把加密通信过程详细写出；（3）如果用户A1要把信息x=3同时完成加密和签名后发送给用户A2，试把加密通信过程详细写出解 （1）计算得n=pq =13×17=221，(n) =（p1）（q1）=12×16=192随机选取与192互素，且满足1e1、e2192的正整数e1=7，e2=13，分别建立同余方程e1x1(mod(n)， e2 x1(mod(n)，即7 x1(mod192)，13x1(mod 192)解同余方程：7 x1(mod19

19、2) 193385(mod192)，因为7与192互素，据消去律得：x55(mod192) 类似地解同余方程得：x133(mod192) 即d1 =55，d2=133 将密钥e1，d1=7，55，e2，d2=13，133分别提供给用户A1和A2使用，并将n =221，e1=7，e2=13公开，d1 =55，d2 =133分别是用户A1和A2的私钥由各自秘密保管，(n) =192则由密钥制作者秘密保管（2）A1在公钥簿上查到A2的公钥e2=13，得到加密函数E2(x) x13(mod 221)对信息x =3加密，得密文y =3 13(mod 221)，因为3 29(mod 221)，349

20、15;9 81(mod 221)，3 881×816561152(mod 221)，所以密文y =3 133 8+4+1152×81×329(mod 221) A1把密文y =29发出A2收到密文y =29后，用自己的私钥d2=133得到解密函数D2(x)x 133(mod221)，用之解密得明文：x= D2 (y)y 133(mod221)29133(mod221) 用与上述同样的方法先计算得29481(mod221)，2912835(mod221)，得到：x=29133 =29128+4+135×81×293(mod221) A2就得到了明

21、文信息x=3（3）A1用自己的私钥d1 =55得到解密函数D1(x)x 55(mod221)对信息x=3签名得：y =D1(x)=355(mod221)，然后查得A2 的公钥e2=13得到加密函数E2(x)x13(mod221)对y加密，得z = E2(y)=（355）13(mod221)3715(mod221) 由本例第（2）小题知：3 1329(mod221)算得：3 26178(mod221) ， 3 5281(mod221)，3 104152(mod221) ，3 208120(mod221) ，3 41635(mod221)，从而z = 37153 416+208+52+26+1335×120×81×178×29 211(mod221) 然后A1将经