理学论文：“不可破译”的密码

密码在当今社会生活中的作用可以说十分巨大，除了众所周知的军事国防方面的应用外，现代金融、贸易、生产等无不在大规模使用密码．计算机网络的广泛应用，使人们对密码的依赖达到了新的高度，在千百万台计算机联结成的因特网上，用户的识别基本上是靠密码．密码被破译就会产生危及安全的极严重的后果．计算机"黑客"的作为，即为密码破译的一例，连美国国防部的计算机都未能幸免，可见密码编制的难度了．
　?由大整数因数分解的困难，人们研制成功一种"不可破译"的密码：ＲＳＡ体制密码（见本刊2000年第6期《大整数的因数分解问题》一文）．ＲＳＡ密码是一种公开密钥密码，说它"不可破译"是形容破译之难，不过的确至今尚没找到破译的理论工具．
　?一般密码编制理论中，称要传递的原文为"明文"，经加密后实际传递的是密码构成的"密文"，收信方则将其解密，恢复为明文使其可理解，就完成了通信任务．这其中加密和解密要用通信双方约定的方法，这一方法就称为密钥．更一般地，人们首先给定一个加密算法，不太严格地说，可把这一算法视为函数，函数的值就是密钥，而解密算法可以说是加密算法的一个反函数，使用同一个密钥（原函数的值）可将密文惟一地译成明文．
　?密码的关键就在于通信双方约定密钥而不被外界所知，外界对密码的破译也就指向密钥了．而且为了防止外界可能的破译，就应尽力使外人不可能积累在同一密钥下的许多密文，否则可用统计分析法等确定出密钥，世界战争史、外交史上有许多破译成功的例子．这样就经常变换密钥，重要的通信要每天一换甚至通一次信换一次．
　?这么频繁换的密钥怎样送给对方？如果随其他信息（用无线电或网络）易于失密，每次派专人送又不可能，怎样解决这一问题呢？这就是ＲＳＡ密码的长处了，它把密钥分成加密钥和解密钥．如Ａ和Ｂ通信，Ａ把加密钥公开送达Ｂ（可用明码电报或与上次通信同时），不怕外人知道，所以叫公开密钥，而解密钥留在自己处不送达Ｂ，Ｂ收到公开密钥后，用它加密要给Ａ的信息，然后送回Ａ（这也无须特别秘密），则Ａ可用手中的解密密钥解密．
　?外人没有解密密钥，就无从破译密码了，那么加密钥和解密钥就没有关系了吗？当然不是，否则就无法解密了．不过这种关系正是建立在大整数因数分解困难的基础上．换句话说，由公开密钥得出解密钥要进行一个充分大的整数的因数分解，你无法分解也就无法破译．
　?具体的编码过程是，先找出两个不同的大素数ｐ和ｑ，再给定一个数ｒ（一般是用计算机产生一个随机数或至少一个伪随机数，也可每次一换），使ｒ与数（ｐ－1）（ｐ－1）互素，这三个数ｐ、ｑ、ｒ就是解密密钥．
　?再求一个数ｍ，使（ｒｍ－1）能被（ｐ－1）（ｑ－1）整除．严格表述为：求ｍ，使
　?ｒｍ≡1（ｍｏｄ（ｐ－1）（ｑ－1））．
　?由于ｒ与（ｐ－1）（ｑ－1）互素，所以ｍ是一定可求出来的（有数论定理保证）．再求出数ｎ＝ｐｑ．ｍ、ｎ为加密密钥，即公开密钥．
　?具体的加密方法为，设明文为ｘ，可把ｘ视为（或变为）一个大整数，设ｘ＜ｎ，若ｘ≥ｎ，则将ｘ表示为ｓ进位的形式（ｓ≤ｎ，常用ｓ＝2ｔ形式）的数，使其每一个数位上的数都小于ｎ，再分数位进行编码．求一个数ｙ（0≤ｙ＜ｎ）使
　　ｙ≡ｘｍ（ｍｏｄｎ）（可理解为，使（ｙ－ｘｍ）能被ｎ整除），ｙ就是用ｍ、ｎ密钥加密后的密文．
　?解密过程为，求
　?ｚ＝ｙｒ（ｍｏｄｎ）（0≤ｚ＜ｎ），
　?在限定的条件（0≤ｙ＜ｎ，0≤ｚ＜ｎ）下有（可严格证明）
　　δ＝ｘ，
　　即得出明文．
　?外人要想破译密码，就必须由ｍ、ｎ求出数ｒ来．
　?由此可见，要找到ｒ必须由ｎ得出ｐ和ｑ，即对ｎ进行因数分解，如ｐ、ｑ取得相当大，即ｎ相当大，由于分解困难，无法破译这一密码．