CTF现代密码之RSA之数论

标签: 算法  数学建模  powerdesigner  密码学  xhtml

亲爱的,关注我吧

10/30

文章共计2345个词

预计阅读8分钟

如果有伙伴发现这篇文章小编之前发过

不要惊讶哦

是对文章做了一些更正呀

来和我一起阅读吧

前言:


在 CTF 的密码题目中,RSA 以其加密算法之多且应用之广泛,所以在比赛中是最常见的题目。学习密码学并不难,但首先得打好数学基础,并在攻破密码的学习之路上持之以恒。今天我们就来打开 RSA 加密世界的第一扇门 《数论》

数论基础:



1.素数

2.公约数与公倍数

3.欧拉函数

4.欧几里得算法

5.扩展欧几里得算法

6.同余

7.模运算

8.逆

9.中国剩余定理

10.逆元与同余式定理

1.素数:


定义:

一个大于1的自然数,除了1和它本身外,

不能被其他自然数整除(除0以外)的数称之为素数(质数);

否则称为合数。

如:
3×4 = 12,不是素数。

11除了等于11×1以外,不能表示为其它任何两个整数的乘积,

所以11是一个素数。
关于素数有以下事实:
(1) 如果p是素数,且p | ab (表示 ab 能被 p 整除),则p | a或 p | b,即 p 至少整除 a 与 b 中的一个。
(2)(算术基本定理) 每个整数n ≥ 2,均可分解成素数幂之积:

若不计因数的顺序,这个分解式是唯一的。其中 k ≥ 1,    是两两互不相同的素数,    是正整数。

(3) 素数有无穷多个。

2.最大公约数与最小公倍数


定义 1:

设   是两个整数。如果   且  ,那么 d 就称为是   和   的公约数(或公因数)我们把   和   的公约数中最大的称为   和   的最大公约数,记作

当   时,我们称   和   是互素的。

定义 2:

设   是两个整数。如果   ,那么   就称为是   和   的公倍数。我们把   和   的正的公倍数中的最小的称为   和   的最小公倍数,记作 

3.欧拉函数


定义:

对正整数  ,欧拉函数是小于或等于   的数中与   互质的数的个数,

记作: φ

例如: φ  ,因为   均与   互质。

性质:

(1) 若   为一素数 P,则: φ

(2) 如果 P 是素数,  ,则: φ  =

例如 :求 φ(16),由于 16 = 2×2×2×2,故 φ(16) = (2-1) ×  = 8

(3) 若 n 为任意两个互质的 数   的积,则:φ(a*b) = φ(a) × φ(b)

例:求 φ(40),由于 40 = 5×8,所以 φ(40) = φ(5) × φ(8) = 4×4 = 16

(4)对于整数  ,根据算术基本定理,  可以分解成唯一的形如   ⋯  的分解式,则:

4.欧几里得(Euclid)算法


定义:

  欧几里得算法又称为辗转相除法,用于求两个数的最大公约数。

原理:  =  (     ) ,

1.python 代码实现

2.python 第三方库:

gmpy2.gcd(a,b)     #求 a,b 的最大公约数

Crypto.Util.number

5.扩展欧几里得算法


定义:

  在已知   时,求解一组解  ,使得 

算法输入:两个正整数   和

算法输出:  和   的最大公因数   及满足等式   的整数   和

python 代码实现:

gmpy2 库函数 gcdext()

6.同余


定义:

  设 a,b 是整数, ,如果  ,则称   和   模   同余,记为  (   ),整数   称为模数

  由于   等价于  ,所以  (   ) 与           等价。因此,一般我们总假定模数 

同余的性质
性质 1:

(1)自反性:a ≡ a (mod m)

(2)对称性:a ≡ b (mod m), b ≡ c (mod m) ,则 a ≡ c (mod m)

性质 2:

(1) 若   (   ),  (   )

则:  (   ),  (   )

特别的,对于一个整数 e,都有   (   ),  (   )

(2) 若   (   ),k>0,则 ak ≡ bk (mod mk)

(3)  若   (   ),d 是 a,b 的公因数,则   (mod  )

(4) 若   (   ),d|m,d>0,则: a ≡ b (mod d)

(5) 若   (   ),则:   (mod m)

(6)       = (          )   

(7)       = (     )    

7.模运算


定义:

    模   的运算给出了   对模   的余数,这种运算称为模运算。注意:模运算的结果是从 0 到   的一个整数。

  模运算就像普通的运算一样,它是可交换、可结合、可分配的。而且,对每一个中间结果进行模   运算后再进行模   运算,其作用与先进行全部运算,然后再进行模   运算所得到的结果是一样的。例如:

这些性质对于密码学中的数学计算非常的重要,模运算可以将所有中间结果和最后结果限制在一个范围内。对于一个   位的模数   ,任何、加、减、乘的中间结果将不会超过   位长,这样避免了巨大的中间结果,使得计算机能够有效的处理数据。

如:计算  (mod n),不要直接进行 7 次乘法和一个大数的模运算:

相反,应该进行三次比较小的乘法和三次比较小的模化简:

((  mod n)  mod n)  mod n

这样就可以避免巨大的中间结果出现。

8.逆


定义:

若 m≥1, ,则存在 c 使得:

我们把 c 称为 a 对模 n 的逆,记作   (mod m),在模数已经指明的情况下,有时也记作 

在(a,m)=1 时,我们可以使用扩展欧几里得算法来求 a 的逆元: ,这是因为:扩展欧几里得算法可以找到整数  ,  使得  ,这样   (   )

9.中国剩余定理


中国剩余定理(Chinese remainder theorem,CRT),又称孙子定理,最早可见于中国南北朝时期(公元 5 世纪)的数学著作《孙子算经》中,为一次同余方程组的起源。

定理(CRT):

  设   是两两互素的正整数,

,则同余方程组:

有唯一解:  (   )

其中   (   ),i=1,2,⋯,k

代码实现:

10.逆元与同余式定理


1.模运算重要公式:

(a+b) % m = (a % m + b % m) % m

(a-b) % m = (a % m - b % m) % m

(a*b) % m = (a % m * b % m) % m

 % m = (a % m)  % m

2.威尔逊定理:

若 p 为素数,则:      ⟹ 推导:     ;

其逆定理同样成立。即:若       ,则 p 为素数

3.二次探测定理:

定义:

若   是素数且 0<x<p ,则   仅有的两个解为:

证明:由于      ,所以: -1≡     ,即     

4.费马小定理

若 a 为正整数,P 是一质数,则:GCD(a,p)=1

那么   ≡  ,推论:        

    ,推论:      =    

5.欧拉定理(Euler):

若 a 与 m 互质,则: φ  ≡1 mod

后记:

数论基础的知识点比较杂乱繁多,这篇文章写的时候尽可能的去精简了,其中的定理及公式是必须要牢记于心的,后面的 RSA 加密算法的讲述中我会介绍定理及公式在 RSA 中的应用。

学习完数论基础后,后面我们将开始学习 RSA 的常见攻击算法及加密原理,以及各种工具的使用和 python 第三方库的函数调用。

喜欢就多关注 CNinja 后续文章哦!有错误的地方欢迎大家指出,一起学习。

推荐实验:RSA加密实验 

https://www.hetianlab.com/expc.do?ec=341770ef-9fbc-4d9b-8ddb-191916b928ea

RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。通过本实验,了解RSA加密算法的基本原理。点击文末阅读原文做实验

10/30

欢迎投稿至邮箱:[email protected]

有才能的你快来投稿吧!

戳“阅读原文”我们一起进步

版权声明:本文为qq_38154820原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_38154820/article/details/109396765