大整数分解算法与实践

何为大整数分解？如何实践大整数分解算法？

作者：Safeheron team

封面：Photo by Shubham Dhage on Unsplash

大整数分解

1977 年，基于大整数分解难题的密码体系 RSA 诞生，命名自 Ron Rivest、Adi Shamir 和 Leonard Adleman 三位提出者姓氏的首字母。RSA 算法在公钥密码学上作出重要贡献并对全世界产生重要影响，三位提出者于 2002 年获该年度图灵奖。整数分解问题是当今几乎所有公钥密码安全性领域中最重要的课题之一。

RSA 算法的安全性依赖于大整数分解难题，即

将一个大整数分解成若干大素因子的乘积。

针对小因子的几种典型的大整数分解算法有：

• Pollard’s rho 算法
• Pollard’s p-1 算法
• ECM 算法（Lenstra elliptic curve factorization/elliptic-curve factorization method )

此次我们将介绍 Pollard’s p-1 算法、ECM 算法与 ECM 算法的一个具体实践 —— GMP-ECM。

Pollard’s p-1 算法

ECM 算法

对于这个方法的改进，ECM 方法在 Pollard’s p-1 的基础上引入了随机的椭圆曲线，将原本的乘法群转换为椭圆曲线的点构成的群。椭圆曲线方法是一种基于数论的算法，利用椭圆曲线上的点的性质和运算规则，寻找满足一定条件的因子。

算法概述

一种 ECM 实现 —— GMP-ECM

GMP-ECM 的实现基于原有的 ECM 方法进行了优化。

Stage 1

在 Stage 1 的计算中，GMP-ECM 优化了椭圆曲线的选取与计算。

随机的椭圆曲线生成

椭圆曲线运算

在 GMP-ECM 中使用 Montgomery’s 形式的椭圆曲线，在求点的乘法或加法过程遵循如下规则：

Stage 2

Stage 2 的主要思想为中间相遇（meet-in-the-middle）策略：

算法复杂度

示例

N=0xA2862FB145AC7CE580E0BFF3CEFF42646050F8C611D36A3026E6EFB433B5CDD9EEFBA893E3F25C23A4951BA20992680162934CBDB6876CC791738C140C6EA6EC82938F7E18C5F0760367CF20883DCAB1D6885E222BBC7A1B5D434FD9FC148E387FA9AD69CE708FDDDE3E963F9AB2AF2046A37D7DBA21BC92E6F2A631C3E7770C77C95FAD6F1DC60D9F0645AEF2CC5D03D2151E35443FE0F90F1E2EAE58489C4450C8281EDCC58DDB409C306797C616954ACABCE4881E40ABDD2689A9F7596F29CD5CB42C752DA9306E7DB87CAC8957E3CA165421CF9E1B7220759A10588B386E33FD8E762E92C9F79D50150EF5FCA5F411DE23B8DFFE47A95D48ADDCF4797565

调用解析工具（https://github.com/Safeheron/integer-factorization）使用 GMP-ECM 方法分解：

ecm -c 2  25e4 1.3e8 -mpzmod threads: 2 mod: 1A2862FB145AC7CE580E0BFF3CEFF42646050F8C611D36A3026E6EFB433B5CDD9EEFBA893E3F25C23A4951BA20992680162934CBDB6876CC791738C140C6EA6EC82938F7E18C5F0760367CF20883DCAB1D6885E222BBC7A1B5D434FD9FC148E387FA9AD69CE708FDDDE3E963F9AB2AF2046A37D7DBA21BC92E6F2A631C3E7770C77C95FAD6F1DC60D9F0645AEF2CC5D03D2151E35443FE0F90F1E2EAE58489C4450C8281EDCC58DDB409C306797C616954ACABCE4881E40ABDD2689A9F7596F29CD5CB42C752DA9306E7DB87CAC8957E3CA165421CF9E1B7220759A10588B386E33FD8E762E92C9F79D50150EF5FCA5F411DE23B8DFFE47A95D48ADDCF4797565********** Factor found in step 2: 1021791499165844943393503 21 52761ms

成功找到素因子 1021791499165844943393503。