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

1RSA公开密钥体制及其主要数学基础江西省上犹县教师进修学校(341200)舒昌勇在密码学发展的历史上，1976年是一个值得纪念的年份．这一年，美国斯坦福大学年轻的数学家狄菲（Diffie）和计算机专家海尔曼(Hellman)联名发表了《密码学的新方向》一文，开创了现代密码学的新领域——公开密钥体制（简称公钥体制）．30年来，公钥体制获得了巨大的发展，它不仅消解了传统的秘密密钥体制存在的一些困难，而且解决了信息安全的一些问题，推动了包括电子商务在内的一大批网络应用的深入和发展．1公开密钥体制的提出1．1传统密钥体制遭遇的困难（1）用户的增加使大量密钥管理成为严重问题在传统的秘密密钥保密通信中，每一对发方和收方都要拥有一对密钥：加密密钥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个用户就需一对密钥，整个通信系统一共需要C22000=(2000×1999)÷2=1999000对密钥，每个用户要保管他和其余1999个用户间的1999对密钥，这让我们不难理解巨大的密钥量给密钥管理、分配和为了确保信息安全而对密钥定期更换方面带来的困难．（2）数字签名和身份认证的问题亟待解决在通常的书信和文件中，人们常常用签名、印章或指纹来表明自己的身份，收方也凭此来确认信、文是否来自发方，在数字通信中同样存在这类问题．但发方如何在信息上签名？收方如何确认发方的身份？如何辨认信息是否系伪造或被修改？这些问题因与信息的安全密切相关都亟待解决．1．2大整数因子分解的无奈根据算术基本定理：任何大于1的整数总可以分解成素因数乘积的形式，并且，如果不计分解式中素因数的次序，这种分解式是唯一的．这个定理在理论上十分漂亮，但操作起来对大整数却非易事甚至实际并不可能．表1列出了用现代最快速的分解算法，在大型计算机上分解一个大整数所需的时间．这让我们看到大整表1数分解在目前是一个非常困难的问题．让人未曾想到的是，正是这种困难为一种新的密钥体制的“核心部件”——单向函数的构造提供了重要的机会．1．3公开密钥思想的提出（1）单向函数1976年，狄菲和海尔曼在《密码学的新方向》一文中，提出采用“单向函数”来设计公钥体制的思路．所谓“单向函数”，是指加密函数E和解密函数D的运算都容易实现，但由E求其逆运算D却非常困难．这样，即使把加密函数E和具体的加密与解密的算法过程都公开，如果不知道解密函数D，把密文解密成明文的计算也无法实现．（2）公钥体制的基本思想整数的位数操作次数所需时间501.4×10103.9小时759.0×1012104天1002.3×101574年2001.2×10233.8×109年3001.3×10294.9×1015年5001.3×10394.2×1017亿年2在公钥体制中，密钥管理中心为每个用户设计一对密钥——加密密钥和解密密钥，加密密钥可以公开，称为公钥，解密密钥由用户自己秘密保管，称为私钥．每个用户与其它任何一个用户的密钥都不相同，在他拥有的一对密钥中，公钥与私钥也不相同，而且由公钥推导出私钥也绝不可行．但它们又密切联系着：用公钥加密的信息只能用与之配对的私钥才能解密，用私钥加密的信息也只能用与之配对的公钥才能解密．1．4公钥体制的工作原理设某公司的n个用户要进行保密通信，密钥管理中心分别为每个用户Ai(i=1，2，…，n)设计一对密钥（Ei，Di），将公钥Ei汇编成公钥簿供所有用户查找，将私钥Di秘密提供给用户Ai使用并由Ai秘密保管．当某用户要发信息x给用户Ai时，先在公钥簿上查找到Ai的公钥Ei，用它将明文信息x加密成密文信息y=Ei(x)，然后通过公开信道发给Ai．Ai收到密文信息y后，用私钥Di作用于y：Di(y)=Di（Ei(x)）=x．由于用Ai的公钥Ei加密的密文信息，只有用Ai的私钥Di才能解密成明文信息，所以即使密文信息被他人截获，也无法解密成明文，因而保证了公钥体制通信的安全性．在前述2000个用户秘密通信的问题中，假如采用公钥体制，由于1个用户只需要拥有1对密钥，所以整个通信系统只需2000个密钥对，每个用户也需记忆与保管属于自己的1个私钥就行，与前述相应的1999000对和1999对相比，分别减少了近1000倍和近2000倍！2RSA公钥体制的基本原理其实，由狄菲和海尔曼提出的公钥体制只是一种思想，他们开创性的论文引进了密码学的一种新方法，但同时也给密码学专家提出了一个挑战性的问题：能否设计一个满足公钥体制要求的加密与解密的算法？1977年，美国麻省理工学院的里弗斯特(Rivest)，沙米尔(Shamir)、阿德勒曼(Adleman)联合设计出著名的RSA公钥体制．这种以他们姓氏的首字母命名的密钥体制的主要数学基础是RSA定理，该定理牵涉较多的数论知识，我们先来做些准备．2．1RSA定理相关的数论知识（1）一个大于1的整数p，如果除1和它本身外没有其它正整数因数，称p是素数．（2）若整数a、b的最大公因数为1（记为（a,b）=1），称a、b互素．（3）设n为正整数，a和b为整数，如果a和b被n除后的余数相同，称a和b模n同余．记为a≡b(modn)．称此式为同余式．n能整除a一般可用同余式a≡0(modn)表示．两个整数a、b模n同余的等价说法有：a和b被n除余数相同；a和b在模n的同一个剩余类中；a－b能被n整除；存在整数s，使得a=sn+b．（4）同余式有一些运算性质，比如：①若a≡b(modn)，c=d(modn)，则ac≡bd(modn)．(同余式的乘法性质)特别地，有ka=kb(modn)，k为任意整数．②若a≡b(modn)，d是a、b、n的公因数，则da≡db(moddn)．③若ab≡ac(modn)，且a与n互素，则b≡c(modn)．(同余式的消去律)（5）设n为正整数，则任何一个整数被n除，余数必为0，1，2，…，n-1中的某一个．把整数集中被n除余数同为0，1，2，…，n-1的数分别归为一类，记为[0]，[1]，[2]，…，[n-1]，这样就按模n是否同余把整数集分成n类，其中每一类都称为模n的一个剩余类．显然，每个整数必属于上述n类中的一类，被n除余数不同的数必属于上述的不同类中．若a0，a1，a2，…，an-1分别取自上述n类的不同类中，称a0，a1，a2，…，an-1为模n的一个完全剩余系，该剩余系中的数两两模n不同余．（6）含有未知量的同余式称为同余方程．一次同余方程是最简单的一种，其一般形式为ax≡b(modn)．若a，n的最大公因数d能整除b，则ax≡b(modn)有解，且恰有d个解．若a，3n的最大公因数d不能整除b，则ax≡b(modn)无解．例如一次同余方程7x≡1（mod5），因为（7，5）=1，1整除b=1，所以同余方程有1个解．求解过程为：7x≡1（mod5）≡6≡11≡16≡21（mod5），因7与5互素，由同余的消去律，得其解为：x≡3(mod5)．一般地，解同余方程的步骤为：①判断解的情况；②当同余方程的a、b、n有公因数时，约去公因数化简方程；③利用同余的定义和消去律求方程的解．（7）费马小定理：设任意整数a与素数p互素，则ap-1≡1(modp)．证明：由a与素数p互素，知p不是a的素因数．又因为p也不是1，2，3，…，p－1的素因数，所以a乘以此数列各项所得新数列a，2a，3a，…，(p－1)a各项都不能被p整除．从而a，2a，3a，…，(p－1)a中的每一项只能和数列1，2，3，…，p－1中的一项模p同余．又由于a，2a，3a，…，(p－1)a中的任意两项都不能模p同余（事实上，如果存在不同的两项ra与sa（不妨设0＜r＜s＜p）模p同余，即sa≡ra(modp)，因a与p互素，据同余式的消去律可得s≡r(modp)，与假设r＜s矛盾），所以a，2a，3a，…，(p－1)a中恰有一项和1，2，3，…，p－1中的1同余，恰有一项和1，2，3，…，p－1中的2同余，…，恰有一项和1，2，3，…，p－1中的p－1同余，从而可以建立p－1个同余式．将这p－1个同余式相乘得：a·2a·3a…(p－1)a≡1·2·3…p－1(modp)．因1·2·3…p－1与p互素，由同余的消去律得ap-1≡1(modp)．2．2RSA定理及其证明定理设p、q是不同的素数，n=pq，记(n)=（p－1）（q－1），如果e、d是与(n)互素的两个正整数，并满足ed≡1(mod(n))，则对于每个整数x，都有xed≡x(modn)．分析由同余定义的等价表述，只要证n是xed－x的因数．但n=pq，且p、q都是素数，所以只要证p、q分别是xed－x的因数，即只要证对于每个x，都有xed≡x(modp)……①xed≡x(modq)……②证明式①只要证xed－x≡0(modp)．如果p是x的因数，则上式显然成立；如果p不是x的因数，即p与x互素，由题设ed≡1(mod(n))，知(n)是ed－1的因数，故存在整数k使得ed－1=(n)k=（p－1）（q－1）k，从而ed=1+（p－1）（q－1）k，xed=x1+（p－1）（q－1）k=x·（xp－1）（q－1）k，因p与x互素，由费马小定理ap-1≡1(modp)，可得xed≡x·（1）（q－1）k≡x(modp)．同理可证②式也成立．因此有：xed≡x(modn)．2．3RSA公钥体制的原理以下RSA公钥体制实施的步骤，会帮我们理解它的基本原理：（1）取两个超过100位的大整数p和q，求出n=pq和(n)=（p－1）（q－1）的值．（2）选一个与(n)互素的正整数e，解同余方程ed≡1(mod(n)，得到解d，则｛e,d｝是可供一个用户使用的密钥对．其中e为公钥，d为私钥．（3）构造两个定义域为｛0，1，2，…，n－1｝的函数：E(x)=xe(modn)为加密函数，4D(x)=xd(modn)为解密函数．（4）根据RSA定理，D(E(x))=D(xe)=(xe)d=xed≡x(modn),即在D(x)和E(x)的作用下，经加密和解密后，明文信息x变换为密文y后又恢复为明文x．所以E(x)和D(x)是互逆的．（5）把供某用户使用的私钥d交该用户，并将其公钥e和n公开，(n)则由密钥制作者秘密保管．（6）别的用户要与该用户秘密通信时，先将明文信息x用该用户的公钥e建立的加密函数E(x)加密，得密文y=E(x)≡xe(modn)，该用户收到密文y后，用自己的私钥d建立解密函数D(x)解密，得明文x=D(y)≡yd(modn)≡(xe)d≡xed≡x(modn)．为什么这里构建的加密函数E（x）≡xe(modn)是单向函数？因为n是素因数p与q很大的整数，所以即使知道n，也极难求出p和q，从而也无法得到(n)．因此在能查到公钥e的情况下，也不能建立同余方程ed≡1（mod(n)）,不能得到私钥d．故E（x）≡xe(modn)为单向函数．2．4用RSA公钥体制进行数字签名和身份认证RSA公钥体制提出后，人们立刻发现也能用它来解决数字签名和身份认证问题．当甲与乙通信时，把明文信息x先用自己的解密函数对它签名：D甲(x)=y．如果信息内容无需保密，甲就可将经他签名的信息y发给乙．乙收到信息就从公钥薄上查到甲的公钥得到加密函数作用于y：E甲（y）=E甲（D甲（x））=x，得到明文信息x，从而确认信息x是来自甲．如果信息内容需要保密，甲在签名后又在公钥簿上查到乙的公钥得到加密函数，用它对已经签名的信息y加密：E乙(y)=z，然后把z发给乙．乙收到z后，先用自己的解密函数作用于z：D乙(z)=D乙(E乙(