加入星计划,您可以享受以下权益:

  • 创作内容快速变现
  • 行业影响力扩散
  • 作品版权保护
  • 300W+ 专业用户
  • 1.5W+ 优质创作者
  • 5000+ 长期合作伙伴
立即加入
  • 正文
    • 1 RSA算法基本原理
    • 2 RSA密钥计算规则
    • 3 RSA密钥计算实例
    • 4 总结
  • 推荐器件
  • 相关推荐
  • 电子产业图谱
申请入驻 产业图谱

嵌入式基础知识-RSA非对称加密基本原理

2023/10/30
2131
阅读需 7 分钟
加入交流群
扫码加入
获取工程师必备礼包
参与热点资讯讨论

之前的文章:嵌入式基础知识-信息安全与加密,介绍过数据加密的一些基本概念,对称加密的原理比较简单,加密和解密的密钥相同,而非对称加密,两个密钥不同,本篇就来具体介绍RSA这种非对称加密的密钥计算原理。

1 RSA算法基本原理

RSA加密算法是由罗纳德·李维斯特(Ronald Linn Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德尔曼(Leonard Adleman)于1977年共同发明的。它的密钥计算规则可由下图所示。

公钥和私钥的基本特点为:

    公钥和私钥中都有两个数字构成,并且其中一个数字是相同的,即图中所示的N,示例为33公钥有自己特有的数字,即图中所示的E,示例为3私钥有自己特有的数字,即图中所示的D,示例为7


公钥加密的过程为(对明文中的每个字符分别解密,示例为加密其中一个字符):

    先对明文求E次幂再将结果对N取余

私钥解密的过程与加密过程类似:

    先对密文求D次幂再将结果对N取余

2 RSA密钥计算规则

上面介绍了RSA加密解密的基本过程,那RSA的密钥(公钥和私钥),怎么计算得到呢?

RSA的密钥计算,需要用到质数和欧拉函数的知识。

质数的概念如果忘了,后面会再介绍。

欧拉函数暂不展开讲解,记住公式即可。

下面就来看下RSA密钥的计算步骤。

2.1 计算步骤

RSA密钥(公钥和私钥)的计算步骤可分为如下五步:

第一步:取两个质数,如p=3,q=11

第二步:质数相乘,N=pxq=3x11=33

第三步:欧拉函数,T=(p-1)x(q-1)=2x10=20

第四步:选公钥E,需满足以下条件:

可以从小开始选,选E=3,因此公钥为(3, 33)

      • 是一个质数1<公钥<T不是T的因子

第五步,计算私钥D,公式为**(DxE)%T=1**,解得D=7,因此私钥为(7,33)

RSA密钥的计算规则是公开的,那破译的难点在哪里呢?

其实,在实际使用时,两个质数尽量取大,转换成二进制后1024个二进制位或者更多,位数越多越难破解。

对于RSA的破解难度分析:

    公钥(E,N)是公开的,要想破解密钥,就是求出D根据公式(DxE)%T=1,E是已知的,下一步就是要获取到T,而T=(p-1)x(q-1),与两个质数有关虽然N=pxq,N也是已知的,但如果这两个质数设置的非常大,N和T也就会很大而对于大数的质数分解,是很难计算的,这就是RSA算法难破解的原理了

2.2 质数简介

上面说到,RSA密钥的计算,需要用的质数,那质数的概念,是否还熟悉呢?

质数是小学数学中就学过的知识点,不过平时用的不多,这里再简单回顾以下。

质数(也叫素数),指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。

质数的一些性质:

    质数p的约数只有两个:1和p算术基本定理:任一大于1的自然数,要么本身是质数,要么可以分解为几个质数之积,且这种分解是唯一的质数的个数是无限的若n为正整数,在n^2到(n+1)^2之间至少有一个质数若n为大于等于2的正整数,在n到n!之间至少有一个质数

可以写一段代码,求取一定范围的质数,感受一下质数有哪些。

代码怎么写呢?还是可以看下小学课本:

Python编写的打印5000以内质数的代码如下:

#判断是否是质数:大于1,不等于2,是否为奇数,是否有约数'''
def isPrime(num):
    if num > 1:
        if num>2:
            if num%2==1:
                for i in range(2, int((num-1)/2)): 
                    if num%i == 0:
                        return False #有约数
                return True #无约数
            return False #3以上的偶数
        return True #等于2
    return False #小于2

if __name__ == '__main__':
    prime_list = []
    for i in range(5000):
        if isPrime(i):
            prime_list.append(i)
    print(prime_list)

这里列举5000以内的质数:

3 RSA密钥计算实例

题目:RSA算法中,选择两个质数,p=11,q=17,加密密钥为e=23,且求解密密钥。

分析:按照RSA算法的基本原理,N=pxq=11x17=187,T=(p-1)x(q-1)=10x16=160,而E=23,

根据(DxE)%T=1,即(Dx23)%160=1,解得D=7

4 总结

本篇介绍了RSA这种非对称加密算法的加密解密基本过程,以及公钥和私钥的计算基本步骤,并补充介绍了质数的相关概念,最后通过一个实例来简单体会下RSA密钥的计算。

推荐器件

更多器件
器件型号 数量 器件厂商 器件描述 数据手册 ECAD模型 风险等级 参考价格 更多信息
FM25CL64B-GTR 1 Cypress Semiconductor Memory Circuit, 8KX8, CMOS, PDSO8, SOIC-8

ECAD模型

下载ECAD模型
$4.24 查看
NX2012SA-32.768K-STD-MUB-1 1 Nihon Dempa Kogyo Co Ltd Parallel - Fundamental Quartz Crystal, 0.032768MHz Nom, ROHS COMPLIANT PACKAGE-2
$7.18 查看
NC7WZ17P6X 1 onsemi TinyLogic UHS Dual Buffer with Schmitt Trigger Inputs, 3000-REEL

ECAD模型

下载ECAD模型
$0.12 查看

相关推荐

电子产业图谱

控制科学与工程硕士,日常分享单片机、嵌入式、C/C++、Linux等学习经验干货~