rsa算法基本流程及签名流程

1、RSA 算法及其实现RSA 加密算法是目前应用最广泛的公钥加密算法，特别适用于通过 Internet传送的数据，常用于数字签名和密钥交换，被国际上的一些标准化组织ISO、ITU、SWIFT 作为标准来采纳。1.1 RSA 算法的基本原理独立地选取两个大素数(保密）。计算(公开），其中为欧拉函数值(保密)。随机选取一整数 e，满足，，e 是公开的密钥即公钥。用 Euclid 算法计算 d，，d 是保密的密钥即私钥。加密变换：对明文，密文为。解密变换：对密文,明文为。其中，加密变换、解密变换两步也可以改为用 d 加密，e 解密，就变成签名和验证过程。1。2 RSA 算法的实现步骤 1 素数的产生对随机数作素性检测，若通过则为素数,否则增加一个步长后再做素性检测，直到找出素数.素性检测采纳 Fermat 测试。这个算法的理论依据是费尔马小定理:假如 m 是一个素数,且 a 不是 m 的倍数,那么根据费尔马小定理。实 际 应 用， 此 对 于 整 数m，需计算，再将结果与 a 比较。假如两者相同，则 m 为素数。选取 a=2，则 a 一定不会是任何素数的倍数.步骤 2 随机数的产生随机数不仅用于密钥生成，也用作公钥加密时的填充字符。它必须具有足够的随机性，以防止破译者掌握随机数的规律后重现密钥的配制过程或者探测到加密块中的明文。因为在计算机上不可能产生真正的随机数，实际采纳周期大于 2256 位的伪随机序列发生器。步骤 3 密钥的生成（1）选择 e 的值为 2623883 或者 94475891；（2)随机生成大素数 p，直到 gcd（e, p—1)=1;（3)随机生成不同于 p 的大素数 q,直到 gcd（e，q—1)=1;(4）计算 n=pq，φ(n)=（p—1)(q—1）；（5）计算 d，；（6)计算 dmod（p-1),dmod(q—1）；(7)计算(q—1)modp；(8）将(e，n) 放入 RSA 公钥；将 n,e,dmod（p-1),dmod（q—1),(q—1)modp放入 RSA 私钥.步骤 4 加密利用 RSA 加密，第一步需要将明文数字化。假定 A、B 统一明文编码方式为空格=00,A=01,B=02，C=03，…，Z=26, 则明文数字化 HI 为 08、09;然后把明文 M分成等长数据块，块长为 s，其中,s 尽可能大.加密规则为：，，x 为明文.加密过程的输入为：明文M，模数 n，公钥 e 或私钥 d,输出为密文。M 的长度不超过，以确保转换为 PKCS 格式时,填充串的数目不为 0。（1）格式化明文。采纳 PKCS 格式：EB=00‖BT‖PS‖00‖M。其中,BT 表示块的类型，PS 为填充串,M 为明文数据，开头为 0 确保...