前段时间笔试,遇到一道题。给定了RSA的公钥(N,E),问给密文x=3加密后的密文为?

由于太久没有做CTF密码题了,看到这道题,我感觉陌生有熟悉。NE代表啥我早已忘记,最后我只能根据以前的印象自己猜测了一个答案写了上去。

因此前几天就把RSA算法又重新复习了一边,并且这次自己用python把算法简单模拟了一下,加深印象。

本文只是自己复习RSA加解密的大致过程,主要参考网上的一些文章,不保证文章正确,很可能有错误。请不要随便参考我的理解哈。本文不涉及任何数学证明(因为我数论基本啥都不会)

算法理解

参数生成

RSA的安全性基于大数质因数分解的困难性。

要执行RSA算法,首先要随机生成两个大质数,记为pq

(具体怎么生成的可能有一些算法吧,我对此不了解,只知道可以用随即大数+素性判定来实现,但这样子效率太低,实际环境中应该不会这么弄)

n=pq
\\
m = (p-1)(q-1) = \phi(n)

这里的\phi表示的是欧拉函数

接下来我们要寻找一组互为乘法逆元的数ed,所谓乘法逆元就是指要满足如下条件

ed=1(mod \ m)

当然这里数ed都要和m互质,不然不存在乘法逆元

当然的一些特殊情况,比如为1等肯定不行

这里的e就是我们接下来加密要用到的密钥,d就是解密要用的公钥

当然因为ed互为乘法逆元,所以公钥和密钥其实交换了也是一样的,在数学上是对称的

这里要获得乘法逆元,我选择的是采用拓展欧几里得算法,不知道实际密码学库里实现是用的什么算法

加解密计算

要加密的信息为x

公钥为(n,e)

enc为加密后的密文

dec为解密后得到的信息

加密过程
enc = x^e \ mod \ n
解密过程
dec = enc^d \ mod \ n

算法保证xdec一定是相同的

证明过程我也不太懂,需要基础数论知识

算法Python实现

import random

#拓展欧几里得算法
#输入a,b
#返回r,rx,ry
#r为a和b的最大公因数
#若r==1,有rx*a+ry*b=1
def extgcd(a,b):
    if b==0:
        return a,1,0
    r,x,y = extgcd(b,a%b)
    rx = y 
    ry = x-a//b*y
    return r,rx,ry

def gete(m):
    while True:
        x = random.randint(2,m-1)
        a,_,_ = extgcd(x,m)
        if a==1:
            return x

def getd(m,e):
    a,x,y = extgcd(e,m)
    assert a==1
    if x<0:
        x += (((-x)//m)+1)*m 
    return x

p = 31
q = 29
n = p*q
m = (p-1)*(q-1)
e = gete(m)
d = getd(m,e)
print("m={}".format(m))
print('public key is (n={},e={})'.format(n,e))
print('secret key is (n={},d={})'.format(n,d))
assert (e*d)%m==1

def encrept(s):
    s = [ord(c) for c in s]
    # print('step 1:',s)
    s = [(item**e)%n for item in s]
    # print('step 2:',s)
    return s

def decrept(s):
    # print('step 3:',s)
    s = [(item**d)%n for item in s]
    # print('step 4:',s)
    s = [chr(item) for item in s]
    return ''.join(s)

test_str = 'hello world'
encrept_str = encrept(test_str)
decrept_str = decrept(encrept_str)
print('test str:',test_str)
print('encrepted str:',encrept_str)
print('decrepted str:',decrept_str)

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注