CryptoHack Writeup——Modular Exponentiation：理解RSA中的模幂运算

平台：CryptoHack
分类：RSA
难度：⭐☆☆☆☆
知识点：RSA、公钥密码、模幂运算、Pythonpow()函数

前言

最近在学习《应用密码学》课程时，为了更深入理解 RSA 算法的基本原理，我选择了 CryptoHack 平台进行练习。CryptoHack 是一个专注于密码学学习的在线平台，通过大量循序渐进的题目帮助学习者掌握密码学理论与实践。

RSA 模块中的第一道基础题Modular Exponentiation看似简单，但实际上涉及整个 RSA 算法最核心的数学运算——模幂运算（Modular Exponentiation）。RSA 加密、解密、数字签名以及密钥验证等过程，都离不开这一运算，因此理解它对于后续学习 RSA 十分重要。

本文将结合题目，对模幂运算的数学原理、Python 实现方式以及在 RSA 中的作用进行分析，并记录自己的解题过程。

一、题目介绍

题目内容如下：

All operations in RSA involve modular exponentiation.

题目要求计算：

[101^{17}\bmod 22663]

并得到正确结果。

从表面来看，这只是一个数学计算题，但实际上是 RSA 加密过程中最基础的一步。

RSA 的加密公式为：

[c=m^e\bmod n]

其中：

• (m)：明文

• (e)：公钥指数

• (n)：模数

• (c)：密文

可以发现，本题实际上就是在模拟 RSA 的一次加密过程。

二、什么是模幂运算？

模幂运算（Modular Exponentiation）指的是：

[a^b \bmod n]

即：

先计算指数，再对结果取模。

例如：

[3^4\bmod5]

计算过程：

[3^4=81]

然后：

[81\bmod5=1]

因此答案就是：

[1]

虽然这个例子比较简单，但如果指数变成：

[2^{65537}]

就已经是一个拥有上万位数字的整数，普通计算几乎无法完成。

因此，RSA 不可能真的先计算完整的大整数，再取模，而是采用更加高效的算法——快速模幂算法（Fast Modular Exponentiation）。

三、为什么 RSA 要使用模幂运算？

RSA 属于公钥密码算法。

其加密过程为：

[c=m^e\bmod n]

解密过程为：

[m=c^d\bmod n]

数字签名过程：

[s=m^d\bmod n]

验证签名：

[m=s^e\bmod n]

可以看到：

整个 RSA 几乎所有计算都可以归结为：

[a^b\bmod n]

因此模幂运算可以说是 RSA 最核心的数学操作。

如果没有高效的模幂算法，RSA 在实际网络通信中几乎无法使用。

四、快速模幂算法简介

假设直接计算：

101^17

会得到一个非常大的整数。

如果指数达到几万甚至几十万：

计算量会急剧增加。

快速模幂算法利用了指数的二进制展开，将复杂度从：

[O(n)]

降低到：

[O(\log n)]

其基本思想就是：

不断平方（Square）和按位乘（Multiply）。

例如：

17 ↓ 10001（二进制）

因此：

[101^{17}101^{16}\times101]

而：

[101^{16}((101^2)^2)^2)^2]

每一步计算结束后立即取模：

(ans × base) % mod

这样可以保证中间结果始终不会变得特别巨大。

五、Python 中如何实现模幂运算？

Python 已经内置了高效实现。

语法如下：

pow(base, exponent, modulus)

例如：

print(pow(3,4,5))

输出：

1

相比：

(3**4)%5

pow()的效率要高得多。

因为：

pow()

底层就是快速模幂算法。

六、解题过程

题目要求计算：

101^17 mod 22663

Python 代码十分简单：

result = pow(101,17,22663) print(result)

运行后即可得到正确答案。

整个过程实际上只有一行代码。

虽然代码很简单，但是背后的数学原理却十分重要。

如果以后 RSA 的参数变成：

2048 位 4096 位 8192 位

仍然可以通过：

pow()

快速完成计算。

这也是现代密码学软件普遍采用的方法。

七、如果不用 pow() 会怎样？

很多初学者可能会写成：

(101**17)%22663

虽然本题依旧能够得到正确结果。

但是如果 RSA 中：

e=65537

或者：

d 拥有几千位

那么：

101**65537

就需要先生成一个极大的整数。

不仅速度慢，而且占用大量内存。

因此实际开发中一般不会这样写。

八、模幂运算在密码学中的应用

除了 RSA，模幂运算还广泛应用于其他密码算法。

例如：

1、Diffie-Hellman 密钥交换

双方通过：

[g^a\bmod p]

生成公开信息。

最终得到共同密钥。

2、ElGamal 加密

加密和解密过程中都需要：

[g^k\bmod p]

的计算。

3、数字签名

RSA Signature：

Hash ↓ 私钥指数运算 ↓ 生成签名

本质仍然属于模幂运算。

4、身份认证协议

很多认证协议都会使用：

大整数 ↓ 指数 ↓ 取模

完成身份验证。

因此：

模幂运算几乎贯穿整个公钥密码体系。

九、本题总结

虽然Modular Exponentiation是 CryptoHack RSA 模块中最简单的一道题，但它对应的是整个 RSA 算法最核心的数学基础。

通过本题，我进一步理解了：

• 什么是模幂运算；

• 为什么 RSA 必须使用模幂运算；

• Python 中pow(base, exp, mod)的优势；

• 快速模幂算法在实际密码系统中的重要性。

很多时候，真正困难的密码学算法，其实都是由这些基础数学工具逐步组合而成的。只有扎实掌握模运算、快速幂、欧拉函数、模逆元等基础知识，才能继续学习 RSA、ECC、Diffie-Hellman 等更复杂的密码算法。

参考资料

1. CryptoHack RSA Challenges

2. William Stallings.Cryptography and Network Security

3. Jonathan Katz, Yehuda Lindell.Introduction to Modern Cryptography

4. 《应用密码学》课程教材

5. Python 官方文档——pow()函数

个人总结：
这道题虽然难度不高，但它让我认识到密码学并不仅仅是复杂的数学公式，而是通过高效算法将理论真正应用于现实系统。对于初学者来说，理解模幂运算是学习 RSA 的第一步，也是后续理解密钥生成、加密解密和数字签名的重要基础。