您好,欢迎来到站长目录(28sn.com)!


CTF中的RSA算法(一)

来源:本站原创 浏览:1144次 时间:2019-07-11
-bak main-content">

    最近看c看的头疼了O(≧口≦)O,所以先停下来缓一缓写几篇博客吧。在讲之前我们先来看一个著名网红老师李永乐的视频,了解一下RSA的一些基本知识,一遍不行看两遍,两遍不行看三遍,切记一定要看懂这个视频,否则,下面写的很有可能就看不懂了。虽说密码学和数学相关性很大,但是一步一步的学并没有那么难,我的数学也不好,但是这并不妨碍我做这些密码学的题目,我可以慢慢的学。记住千万不要还没开始就放弃了。    视频链接:https://www.bilibili.com/video/av26639065/

    基本介绍:    RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。    RSA加密算法是一种非对称加密算法。    对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。 假如有人找到一种快速因数分解的算法的话,那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到目前为止,世界上还没有任何可靠的破解RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。    公钥与私钥的产生:(1)进行加密之前,首先找出2个不同的大质数p和q(2)计算n=p*q(3)根据欧拉函数,求得φ(n)=φ(p)φ(q)=(p−1)(q−1)(4)找出一个公钥e,e要满足: 1<e<φ(n) 的整数,且使e和φ(N)互质。。(5)根据e*d除以φ(n)余数为1,找到私钥d。于是: 公钥就是(n,e) 私钥就是(n,d)

加密==> m^e除以n求余数即为c(密文)00解密==> c^d除以n求余数即为m(明文)01既然知道了原理,是不是就应该做一道题练练身了呢02题目:按照RSA算法,若选取两奇数p=5,q=3,公钥e=7,则私钥d为多少?(不要直接偷看答案解析哈)A.6    B.7    C.8    D.9

解析:由p=5,q=3,e=7,可知n=p*q=15; φ(n)=(p−1)(q−1)=8      由ed除以φ(n)余数为1得,7d=1(mod 8)      mod运算(取余)应该大部分人都会吧,不会的话可以去百度一下。enn......如果说上面的题目你已经自己做出来了,或者看懂答案解析了,说明你悟性还是挺高的哈。那下面这道题目呢? O(∩_∩)O~题目来自:Jarvis OJ - Basic - VeryEasyRSA()0403    呀( ⊙ o ⊙ )!数好大,怎么搞,这是手要报废的节奏啊O(≧口≦)O。    enn......怎么可能那么难啊,看看题目名---VeryEasyRSA,所以吧,我们就要上我们的工具了--python。俗话说的好”工欲善其事必先利其器“。    下面是RSA中常用到的模块安装,经过我的多次尝试,终于找到了不走弯路的安装方法,这里用的是python2,因为python3的模块安装时会存在各种各样的问题,甚至那个模块python3还没有,python2安装时错误会少一点,而且做rsa的题目时我还没见过哪个大佬用python3,清一色的python2。

  前提条件:基于linux环境安装,确保安装了wget,gcc,make软件,会基本的linux命令。  一共需要安装6个模块(不要随便更改下载链接中的模块版本,我不保证更改后的模块版本适合下面源码安装的编译选项,enn当时我就在这个坑里跳了好久才出来。一定要按照顺序安装,有的模块是依赖前面模块的。)

  1. 检查是否安装了M4模块    命令行命令: man m4    如果没有安装,就先安装一下,网上大部分资料写的都是使用源码写的方式安装,但是可能是编译软件版本的问题,进行m4源码安装时总是安装失败,这就是第一个坑,最后竟然可以直接使用apt-get命令安装,太狠了这个:apt-get install m4
  2. 安装GMP模块
    wget http://39.105.152.218:8000/public/gmp-6.1.2.tar.bz2tar -xf gmp-6.1.2.tar.bz2 

    cd 进入解压后的文件夹

    ./configure --prefix=$HOME/static --enable-static --disable-shared --with-pic

    执行完成之后再执行

    make && make check && make install
  3. 安装MPFR模块(解压,进入目录什么的的命令下面就不写了,和(2)中一样。
    wget http://39.105.152.218:8000/public/mpfr-4.0.2.tar.bz2 
    ./configure --prefix=$HOME/static --enable-static --disable-shared --with-pic --with-gmp=$HOME/static
    make && make check && make install
  4. 安装MPC模块
    wget http://39.105.152.218:8000/public/mpc-1.1.0.tar.gz
    ./configure --prefix=$HOME/static --enable-static --disable-shared --with-pic --with-gmp=$HOME/static --with-mpfr=$HOME/static
    make && make check && make install
  5. 安装gmpy2模块
    wget http://39.105.152.218:8000/public/gmpy-gmpy2-2.1.0a1.zip
    sudo python setup.py build_ext --static=$HOME/static install
  6. 安装libnum模块
    git clone https://github.com/hellman/libnum
    sudo python setup.py install 

        好了,到这里常用的RSA解密的模块都装的差不多了。回到上面的那个题目,我们看看怎么个VeryEasyRSA法。    解题脚本:

#!/usr/bin/python#coding:utf-8#@Author:醉清风import gmpy2p = 3487583947589437589237958723892346254777q = 8767867843568934765983476584376578389e = 65537phi = (p-1)*(q-1)       #φ(n)在写的时候多用phi代替,因为键盘不好敲出来。d = gmpy2.invert(e,phi) #e模phi的逆为d, (e*d)%phi==1 原理上面讲过print d

或者

#!/usr/bin/python#coding:utf-8#@Author:醉清风import libnump = 3487583947589437589237958723892346254777q = 8767867843568934765983476584376578389e = 65537phi = (p-1)*(q-1)d = libnum.invmod(e,phi) #e模phi的逆为d,(e*d)%phi==1 print d

    上面的两种解法只是调用的模块不同,但计算效果是一样的,后面的题目中也会经常使用这些模块,具体想用哪个模块看自己的心情就好。    现在才只是个开始,后面的更有意思,未完待续......

推荐站点

  • 我爱发烧音乐我爱发烧音乐

    我爱发烧音乐囊括了从流行音乐到古典音乐多个类型的音乐作品,专栏推荐最新的音乐,提供音乐排名榜单!可供免费线上收听音乐,歌曲流畅,音效极佳! 网站提供的钢琴以及二胡专栏,可供收听者,陶冶情操,改善心情,是难得的轻音乐典藏!

    www.520fs.com
  • 世纪音乐网世纪音乐网

    世纪音乐网是专业的在线音乐试听MP3下载网站。歌曲总计30余万首,收录了网上最新歌曲和流行音乐,DJ舞曲,非主流音乐,经典老歌,劲舞团歌曲,搞笑歌曲,儿童歌曲,英文歌曲等。是您上网听歌的最佳网站。

    www.ssjj.com
  • 怒江大峡谷网怒江大峡谷网

    怒江大峡谷网内容包括:新闻、要闻、怒江报、视频、文化、民俗、人文、音乐、政务、公告、政策等地方信息。

    www.nujiang.cn
  • 杭州网杭州网

      杭州网是杭州地区唯一的新闻门户网站,由中共杭州市委宣传部、杭州日报报业集团和杭州广播电视集团共同组建的杭州网络传媒有限公司运营。

    www.hangzhou.com.cn
  • 深圳在线深圳在线

      深圳在线 www.szol.net是深圳本地最大、最早的地方生活资讯网站之一,网站名“深圳在线www.szol.net”由南方报业传媒集团编辑委员会总编辑、南方日报社总编辑、南方都市报总编辑、南方书画院名誉院长王春芙亲笔题名,深圳在线www.szol.net团队与深圳热线www.szonline.net、奥一网www.oeeee.com都源于全国最早成立于1996年的知名网络公司——深圳万用网。

    www.szol.net

鄂公网安备 42062502000001号