#

s=’KEY{J2sa42ahJK-HS11III&#125’
key=s.split(‘;’)
flag=’’
for i in key:
flag+=chr(int(i[2:]))
print flag
testtest

RSA

好好学数学啊小同志!

…先简单说一下rsa相关的东西。

RSA 算法的可靠性由其极大整数因数分解的难度决定。

也就是说,极大整数做因数分解愈困难,RSA 算法愈可靠。

在还没找到一种快速因数分解的算法之前,rsa加密还是很可靠的。目前短的 RSA 秘钥可能被强力方式破解。而只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。(只要我跑的足够快,寂寞就追不上我(闭嘴))

最近稍微看了一下相关的东西。然后整理了一下www

a^b是a的b次方啦…忘了应该怎么打出来了orz…

RSA算法涉及到的参数:

p : 大质数p
q : 大质数q
n : n=p*q

欧拉函数:
φ(n) = φ(p) * φ(q) = (p − 1)(q − 1) = n − (p + q − 1)

e : encryption key (public key) (又称加密指数)

d : decryption key (private key) e对于φ(n)的模反元素即e模φ(n)的逆元

m:message(m < n),明文。

c : ciphertext,c≡m^e(mod n),即密文

加密过程:

1.随机选择两个不相等的质数p和q。

2.计算p和q的乘积n。

n的长度就是密钥长度。

如n为3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。(实际应用中,RSA密钥一般是1024位,重要场合则为2048位。)

3.计算n的欧拉函数φ(n)

φ(n) = (p-1)(q-1)

4.随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质,将e作为公钥。

5.计算e关于φ(n)的模反元素d,作为私钥。

计算过程:

模反元素即模逆元(参考离散数学或者信安数学基础或者百科学习)

简单来说,就是一个整数d可以使ed乘积被φ(n)除的余数为1:
ed ≡ 1 (mod φ(n))(也就是ed%φ(n)=1)
即求解

ed+φ(n)x=1(x未知,但是求得e和φ(n)就可以通过扩展欧几里得算法得到d的值,具体可以参考最底下ctf中rsa题目解析第二个链接。)

公开e,保留d。

公钥为(n,e),私钥为(n,d)

针对明文M,进行加密:C=(M^e)%n,得到的C即为密文

针对密文C,进行解密,M=(C^d)%n,得到的M即为明文

而在ctf比赛里,一般会给出n值和e值,然后可以在http://factordb.com/或者大质数分解工具里因式分解,得到p,q。然后通过p,q算出φ(n)。通过φ(n)和e,算出d。

jarvis oj一道简单的rsa:veryeasyrsa

已知RSA公钥生成参数:

p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537

求d 

py脚本如下。
modinv函数就是求模逆的函数。

import math


def egcd(a, b):
     if a == 0:
         return (b, 0, 1)
     else:
         g, y, x = egcd(b % a, a)
         return (g, x - (b // a) * y, y)


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not    exist')
    else:
        return x % m


p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537
d = modinv(e, (p - 1) * (q - 1))
print d

明文就是m=pow(c,d,n)

(ps.当e=1时,c≡ m mod n,因为n远大于c,m=c.也就是明文密文是一样的…实际上没加密啦…)

有的时候,会出现多个n的公约数分解.

比如给了2个n(n1,n2),q的值相同(而p不同所以有多个n),e的值和密文c。py脚本如下:

def gcd(a, b):
    if a < b:
        a, b = b, a

    while b != 0:
        temp = a % b
        a = b
        b = temp

    return a



n1=。。。
n2=。。。

p = gcd(n1,n2)

print p,"\n\n",n1 // p

就可以算出q的值啦。

也就是最后输出的n1除以p

老方法,知道p,q就知道φ(n)。通过φ(n)和e,算出d。

其他:

一般题目不会直接给参数,可能给比如pem文件(后缀.enc/.pem),可以通过linux下openssl命令提取。linux下命令:

openssl rsa -pubin -text -modulus -in warmup -in 喵.pem

openssl rsautl -encrypt -in FLAG -inkey public.pem -pubin -out 喵.enc

在p,q的取值差异过大,或者p,q的取值过于相近的时候,Format算法与Pollard rho算法都可以很快将n分解成功。

(利用开源项目yafu可以自动化实现,语句直接:factor(n)

也可以通过linux下的openssl命令提取。

RSA入门级别的大概就这样…
以后大概会补充后续?…

学习了之后的感受是…
我,我以后一定好好听数学课!(ry

具体算法解析:
   http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

关于rsa公钥指数:
   http://blog.csdn.net/hherima/article/details/52461759

关于ctf中rsa的题目解析:

   http://bobao.360.cn/learning/detail/3058.html
(算法思路)

   http://blog.csdn.net/qq_18661257/article/details/54563017


   http://blog.csdn.net/veritas501/article/details/55257957
(常见类型)

yafu使用:

http://www.mamicode.com/info-detail-1999309.html

记一道MISC图片题(拖延癌晚期)

几个月前实验班考核的一个杂项

这个题是今年实验班考核的时候一个学长出的300分的杂项,然后当时没做出来…回来之后在学长的提示下做出来了otz…

就是一道脑洞题…不过学到了一些新的工具使用。所以总结一下。

最近清理window虚拟机找到了一些做的时候的截图什么的想起来了这事。觉得有的东西还是觉得记录一下。(虽然本拖延癌晚期患者已经拖了几个月…)

原本好像是zip伪加密方式(记不太清楚了),做出来可以得到一张jpg图。

这是一张守望屁股里黑百合的jpg图。
wm.jpg

用16进制分析工具分析一下。
ffd8文件头没问题,搜索一下文件尾ffd9。

a.png

可以看到ffd9的文件后包含了一些其他的东西。
这是16进制的编码,通过在线进制转换回ascii码,得到一堆的坐标点。

2.png

学习到了一个工具…能将坐标点转化成图像的——gnuplot。

通过命令plot直接就能将一组坐标转化为图片,真四神奇啊!

但是用gnuplot跑的时候发现有个问题…它不能直接识别(x,y)这种格式的。

我:“……”

233.jpg

…然后找了很久,找了个文本编辑器。editplus,轻量级,还能直接转html格式,以及统计字数什么的…非常方便,运用替换(,)为空,然后首行缩进,将文本导出为3.txt。

5.png
这种格式)

然后运行gnuplot。

6.png

然后扫描二维码flag就出来了…

总结一下常用的图片文件头标识:
JPEG/JPG - 文件头标识 (2 bytes): FF D8 FF,文件结束标识 (2 bytes): FF, D9     
PNG - 文件头标识 (8 bytes)   89 50 4E 47 0D 0A 1A 0A    
GIF - 文件头标识 (6 bytes)   47 49 46 38 39(37) 61                        G  I  F  8  9 (7)  a
BMP - 文件头标识 (2 bytes)   42 4D      B  M
以及
gnuplot直接用“plot 函数/文件”可以导出图片(更复杂的操作应该还用不上)

这道题就是脑洞题…

因为以前做的图片题都是hex/binwalk+foremost/stegsolve/(上次实验班考核还新get了一个silenteye的图片加密解密工具)

不过get了新的姿势,还是记一下。