【视频讲解】PicoCTF 2022 使用Python完成mod逆运算

相关阅读

在网络安全入门的探讨中，推荐了Pico ctf

在上期视频中我们教大家通过简单的Python脚本完成一道mod运算的题，今天稍微加大一点点难度，看看你还会吗

知识铺垫：什么是模逆元素？（什么是模的逆元？）

视频讲解

今天我们借此机会，给大家讲解一下如何使用Python求模的逆元

下面一组数字

104 290 356 313 262 337 354 229 146 297 118 373 221 359 338 321 288 79 214 277 131 190 377 

我们对每个数字mod 41求它的逆元，然后将取得的结果继续进行映射，结果是1-26 是字母表（大写），27-36 是十进制数字，37 是下划线。

我们给大家举个例子就能明白了！就拿第一个104来说，我们想求它的模逆元素，那就相当于求

104^-1mod41

上面的式子可以转换为

(104 × 它的模逆元素) mod 41 =1

我们可以通过wolframalpha进行运算

它的模逆元素是28，我们可以进行验证

(104 × 28) mod 41 = 1

可以验证是没问题的

104 × 28 = 41 × 71 + 1

对于上面的CTF题，第一个数字对应28还没结束！

因为，我们还要按照题目要求进行映射，它在27-36之间，则应该转为十进制数字，0123456789

28是第二个，因此就变成1了，题目中还有很多数字，它们的做法也是如此！

其实我们无需知道如何去求解，只要会用函数就行了

对于，x * y == 1 (mod p)

Python里对应的函数

y = pow(x, -1, p)