RSA算 法 中安全大素数的生成 应用数学0801 白钦予 080705003 第一部分.序 RSA算法简介。 RSA是被研究得最广泛的公钥算法，也是第一个能同时用于加密和数字签名的算法。RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。 RSA 的算法涉及三个参数，n、e1、e2。 其中，n 是两个大质数p、q 的积，n 的二进制表示时所占用的位数，就是所谓的密钥长度。e1 和e2 是一对相关的值，e1 可以任意取，但要求 e1与(p-1)*(q-1)互质；再选择 e2，要求(e2*e1)mod((p-1)*(q-1))=1。 满足上述条件后，(n 及e1),(n 及e2)就是密钥对。 RSA加解密的算法完全相同,设A为明文，B为密文，则：A=B^e1 mod n；B=A^e2 mod n； RSA算法密钥的生成是很麻烦的，原因就是生成大素数不是一个容易的事情，目前能预测保证2030年之前足够安全的RSA密钥长度是2048bit，所以能否快速生成大素数构造RSA的密钥是一个影响RSA实际使用的至关重要的因素。 下面文章便从数学以及计算科学的角度，提供一种生成大素数的方式。 第二部分.大素数生成法 素数生成流程分为素数搜索、素数预筛选、素数测试三个阶段。 一 ． 素 数 搜 索 。 首 先 ， 我 们 有 两 种 方 法 可 以 选 取 。 常 用 的 搜 索 方 法 有 随 机 搜 索 法 和 随 机 递 增搜 索 法 两 种 。 它 们 分 别 是 ： 随 机 搜 索 法 :随 机 产 生 一 个 奇 数 p1进 行 素 数 测 试 ,若 是素 数 ,则 结 束 ;否 则 ,重 新 随 机 产 生 一 个 奇 数 P2进 行 素 性 测 试 ,直 至 找 到 一 个 素 数Pt。 由 于 素 数 分 布 的 不 确 定 性 ， 尤 其 是 在 于 高 达 2000以 上 位 数 的 等 级 上 素 数 的 分布 更 加 无 序 ， 可 见 这 种 方 法 实 践 起 来 是 很 耗 时 的 。 随 机 递 增 搜 索 法 比 起 之 前 的 方 法 要 好 一 点 ： 随 机 产 生 一 个 奇 数 ,对 以 该 数 为起 点 的 奇 数 依 次 进 行 测 试 ,直 至 找 到 一 个 素 数 。 这 种 方 法 相 对 于 随 机 搜 索 法 ， 在速 度 上 有 一 定 的 提 高 ， 但 是 并 没 有 本 质 上 的 区 别 。 其 实 对 于 素...
