专栏首页IT 茂茂RSA 算法简述

RSA 算法简述

RSA是什么

  • 计算机的加密技术分为对称加密和非对称加密两类。在对称加密中,信息的加解密使用同一秘钥key,其可简化加解密的过程,较为简单,但不足之处在于由于加解密使用同一个key,信息传送双方都要接触这个key,密钥key更容易泄露。
  • 在公开密钥加密即非对称加密中,密钥分为公钥PK(发送方通过PK对数据加密,然后发送给接收方,PK可公开),私钥SK(SK解密方保存,接收方通过SK对密文解密,SK不公开)。RSA公钥密码体制是最具代表性的非对称加密方式。

RSA算法原理

  • RSA定理:若P和Q是两个相异质数,另有正整数D和E,其中E的值与
  • (P-1)(Q-1)的值互质,并使得DE%(P-1)(Q-1)=1,有正整数M,且M<PQ,设:
  • C=ME%PQ,B=CD%PQ,则有M=B。

生成公钥和密钥

  • 随意选择两个大的素数P和Q,且P不等于Q
  • 令N=PQ
  • 令T=(P-1)(Q-1)
  • 选择一个整数E,作为一个密钥,使E与T互质(即E与T的最大公约数为1),且E必须小于T
  • 由公式DE%T=1,计算得到D的值,作为另一密钥
  • 将(N,E)作为公钥,(N,D)作为私钥,当然也可互换。

用公钥加密信息

  • 发送方收到公钥(N,E)后,通过公钥对数据进行加密,操作如下:
  • 明文:M
  • 加密:ME%N=C
  • 密文:C

用私钥解密信息

  • 接收方收到密文C后,通过私钥(N,D)进行解密,得到明文M,操作如下:
  • 密文:C
  • 解密:CD%N=M
  • 明文:M

RSA算法模拟

为了计算方便,选取较小素数

生成公钥和密钥

  • 取P=11,Q=13
  • 令N=PQ=11*13=143
  • 令T=(P-1)(Q-1)=10*12=120
  • 取E=7
  • 由公式DE%T=1,D*7%120=1得:D=103
  • (143,103)作为公钥,将(143,7)作为私钥。

用公钥加密信息

  • 明文:取M=2
  • 加密:ME%N=C,2103%143=63
  • 密文:C=63

用私钥解密信息

  • 密文:C=63
  • 解密:CD%N=M,637%143=2
  • 明文:M=2

RSA的应用:数字签名

数字签名是实现安全的核心技术之一,它的实现基础就是RSA加密技术,它是RSA的典型应用。 以往的书信或文件是通过亲笔签名或印章证明其真实性的,但在计算机网络中,要解决报文的验证问题,就要使用数字签名,其必须保证以下几点:

  • 接受者能够核实发送者对报文的签名
  • 发送者事后不能抵赖对报文的签名
  • 接受者不能伪造对报文的签名
  • 在现有的多种实现数字签名的方法中,采用公开秘钥算法比常规算法更容易实现。
  • 采用RSA实现数字签名的过程:
  • 发送者A用其私钥SKA对报文M进行运算,将结果DSKA(M)发送给接受者B。
  • 接受者B用已知的A的公钥得出EPKA(DSKA(M))=M。
  • 因为除了A没人有A的私钥SKA,所以除了A没有人能产生密文DSKA(M),这样,报文M就被签名了。用私钥加密的报文发给对方,对方只能用持有的公钥解密,这样就实现了核实发送者对报文的报文的签名。
  • 如果发送者A要抵赖曾经发送过报文M给用户B,则用户B可将M和DSKA(M)出示给第三方监管机构,第三方很容易用公钥PKA去证实A确实发送报文M给用户B。反之,若用户B将M伪造为M’,则用户B就不能在第三方面前出示DSKA(M’),这样就证明了用户B伪造了对报文M的签名。由此,可看出,实现数字签名的同时也实现了对报文来源的鉴别。

RSA算法的缺点

再强的加密算法,也有被破解的一天。RSA算法是被研究得最广泛的公钥算法,从提出到现在经历了各种攻击,被普遍认为是目前最优秀的公钥方案之一。 RSA的缺点主要有两点:

  • 产生密钥很麻烦,由于素数产生技术的限制,难以做到一次一密。
  • 分组长度太大,为保证安全性,N至少要600bit二进制位以上,运算代价高,速度慢。RSA算法的安全性依赖于大数分解,对于一个大数N,没有有效的方法能够将其分解,从而在已知(N,D)的情况下,无法获得E,同样在已知(N,E)的情况下无法求得D。目前,SET协议中要求CA采用2048bit二进制位长的密钥,其他实体使用1024比特的密钥。现在小于1024比特的N已被证明是不安全的,因此不应使用小于1024比特的RSA,最好使用2048位的N。

公钥加密

  • 假设一下,我找了两个数字,一个是1,一个是2。我喜欢2这个数字,就保留起来,不告诉你们(私钥),然后我告诉大家,1是我的公钥。
  • 我有一个文件,不能让别人看,我就用1加密了。别人找到了这个文件,但是他不知道2就是解密的私钥啊,所以他解不开,只有我可以用
  • 数字2,就是我的私钥,来解密。这样我就可以保护数据了。
  • 我的好朋友x用我的公钥1加密了字符a,加密后成了b,放在网上。别人偷到了这个文件,但是别人解不开,因为别人不知道2就是我的私钥,
  • 只有我才能解密,解密后就得到a。这样,我们就可以传送加密的数据了。

私钥签名

  • 如果我用私钥加密一段数据(当然只有我可以用私钥加密,因为只有我知道2是我的私钥),结果所有的人都看到我的内容了,因为他们都知
  • 道我的公钥是1,那么这种加密有什么用处呢?
  • 但是我的好朋友x说有人冒充我给他发信。怎么办呢?我把我要发的信,内容是c,用我的私钥2,加密,加密后的内容是d,发给x,再告诉他
  • 解密看是不是c。他用我的公钥1解密,发现果然是c。
  • 这个时候,他会想到,能够用我的公钥解密的数据,必然是用我的私钥加的密。只有我知道我得私钥,因此他就可以确认确实是我发的东西。
  • 这样我们就能确认发送方身份了。这个过程叫做数字签名。当然具体的过程要稍微复杂一些。用私钥来加密数据,用途就是数字签名。

    总结:公钥和私钥是成对的,它们互相解密。

    公钥加密,私钥解密。

    私钥数字签名,公钥验证。

举例

比如有两个用户Alice和Bob,Alice想把一段明文通过双钥加密的技术发送给Bob,Bob有一对公钥和私钥,那么加密解密的过程如下:

  • Bob将他的公开密钥传送给Alice。
  • Alice用Bob的公开密钥加密她的消息,然后传送给Bob。
  • Bob用他的私人密钥解密Alice的消息。

  上面的过程可以用下图表示,Alice使用Bob的公钥进行加密,Bob用自己的私钥进行解密。

公钥算法与私钥算法

私钥算法

私钥加密算法,又称 对称加密算法,因为这种算法解密密钥和加密密钥是相同的。也正因为同一密钥既用于加密又用于解密,所以这个密钥是不能公开的。

公钥算法

公钥加密算法,也就是非对称加密算法,这种算法加密和解密的密码不一样,一个是公钥,另一个是私钥:

公钥和私钥成对出现

  • 公开的密钥叫公钥,只有自己知道的叫私钥
  • 用公钥加密的数据只有对应的私钥可以解密
  • 用私钥加密的数据只有对应的公钥可以解密
  • 如果可以用公钥解密,则必然是对应的私钥加的密
  • 如果可以用私钥解密,则必然是对应的公钥加的密
  • 公钥和私钥是相对的,两者本身并没有规定哪一个必须是公钥或私钥。

实现数据的安全传输

  • 要实现数据的安全传输,当然就要对数据进行加密了。
  • 如果使用对称加密算法,加解密使用同一个密钥,除了自己保存外,对方也要知道这个密钥,才能对数据进行解密。如果你把密钥也一起传过去,就存在密码泄漏的可能。所以我们使用非对称算法,过程如下:
  • 首先 接收方 生成一对密钥,即私钥和公钥;
  • 然后,接收方 将公钥发送给 发送方;
  • 发送方用收到的公钥对数据加密,再发送给接收方;
  • 接收方收到数据后,使用自己的私钥解密。
  • 由于在非对称算法中,公钥加密的数据必须用对应的私钥才能解密,而私钥又只有接收方自己知道,这样就保证了数据传输的安全性。

公钥算法的缺点

现实中,公钥机制也有它的缺点,那就是效率非常低,比常用的私钥算法(如 DES 和 AES)慢上一两个数量级都有可能。所以它不适合为大量的原始信息进行加密。为了同时兼顾安全和效率,我们通常结合使用公钥算法和私钥算法:

  • 首先,发送方使用对称算法对原始信息进行加密。
  • 接收方通过公钥机制生成一对密钥,一个公钥,一个私钥。
  • 接收方 将公钥发送给 发送方。
  • 发送方用公钥对对称算法的密钥进行加密,并发送给接收方。
  • 接收方用私钥进行解密得到对称算法的密钥。
  • 发送方再把已加密的原始信息发送给接收方。

接收方使用对称算法的密钥进行解密。

总结:

  • 每个用户都有一对私钥和公钥。
  • 私钥用来进行解密和签名,是给自己用的。
  • 公钥由本人公开,用于加密和验证签名,是给别人用的。
  • 当该用户发送文件时,用私钥签名,别人用他给的公钥解密,可以保证该信息是由他发送的。即数字签名。
  • 当该用户接受文件时,别人用他的公钥加密,他用私钥解密,可以保证该信息只能由他看到。即安全传输。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 公钥私钥的那点事儿

    生成秘钥参考官网:https://docs.open.alipay.com/291/105971

    IT茂茂
  • 相见恨晚的超实用网站,一次性分享出来

    IT茂茂
  • Python 【面试总结】

    https://blog.kido.site/2018/12/01/db-and-cache-01/

    IT茂茂
  • 关于公钥与私钥,以及利用它们进行加密和认证

    下一篇,我即将详细分析windows vista下的EFS加密技术。在这之前,先分析一下相关的公钥与私钥、以及相关的加密与认证技术。

    williamwong
  • 公钥能用公钥解吗?

    公钥和私钥通常有可以互相加解密的特性: 将原始信息用公钥加密后,可以使用私钥解密; 将原始信息用私钥加密后,通常可以使用公钥解密。

    葆宁
  • 加密工具类,提供RSA & AES & DES 等加密解密方法工具类介绍加密解密概念使用方法公钥、私钥生成

    用户2141756
  • Spring Boot接口返回及入参RSA加解密

    RSA加密是一种非对称加密。可以在不直接传递密钥的情况下,完成解密。这能够确保信息的安全性,避免了直接传递密钥所造成的被破解的风险。是由一对密钥来进行加解密的过...

    Bobby
  • [Golang软件推荐] RSA公私钥加解密(解决Golang私钥加密公钥解密问题)

    安全是软件开始中很重要的一个环节,在金融场景以及设计资产的场景下更是如此,在加密算法中主要使用较多加密方式分别是对称加密和非对称加密,对称加密中的代表是AES,...

    喵了个咪233
  • 这个轮子让SpringBoot实现api加密So Easy!

    在项目中,为了保证数据的安全,我们常常会对传递的数据进行加密。常用的加密算法包括对称加密(AES)和非对称加密(RSA),博主选取码云上最简单的API加密项目进...

    JAVA葵花宝典
  • linux学习第四篇:克隆虚拟机以及两台linux机器相互登录

    克隆虚拟机 1.      克隆 ? ? ? 之后自己命名克隆的虚拟机并自己选择存放位置,完成克隆 2.      克隆虚拟机之后对新的虚拟机修改网络配置,以免...

    用户1215343

扫码关注云+社区

领取腾讯云代金券