best_CRYPTO

密码学需要数论的知识，一切都要从头开始。

1. crypto基础

1.1 python的模块介绍

1.1.1 binascii模块

binascii模块用于在二进制和ASCII之间转换

>> import binascii

# 将bytes类型的字符串对象转ascii并用十六进制表示
>> str1 = b"hello world"  
>> binascii.b2a_hex(b"hello world")
# 输出 b'68656c6c6f20776f726c64'

# 相反操作
>> binascii.a2b_hex(b'68656c6c6f20776f726c64')
# 输出b'hello world'

>> binascii.hexlify(b"hello world")     # 注解： 同b2a_hex(), 返回bytes类型的字符串对象data 的十六进制表示。 data 的每个字节都转换为相应的2位十六进制表示。因此返回的字节对象的长度是 data 的长度的两倍。
# 输出 b'68656c6c6f20776f726c64'

>> binascii.unhexlify(b'68656c6c6f20776f726c64')     # 注解： 同a2b_hex(), 返回由十六进制字符串 hexstr 表示的bytes类型的字符串对象。 hexstr 必须包含偶数个十六进制数字（可以是大写或小写），否则会引发 Error 异常。
# 输出b'hello world'

1.1.2 math模块

参考资料：

1、Python math 模块与 cmath 模块 https://www.runoob.com/w3cnote/python-math-and-cmath-module.html

1.1.2.1 math.gcd

求两个数的最大公约数

>>> import math
>>> math.gcd(948946465,454545)
5

1.1.2.2 math.log和math.log10

math.log(x) 就相当于数学中的ln(x)，x>0，求底数为e的对数，e = 2.718281828459；

math.log10(x) 就相当于数学中的lg(x)，x>0，求底数为10的对数；

用法如下：

import math
math.log(x[, base])
x -- 数值表达式。
base -- 可选，底数，默认为 e。 

1.1.3 libnum模块

参考资料：

1、libnum, 使用数字( 素数，模块，等等 ) https://www.kutu66.com/GitHub/article_99877

可以使用libnum模块下的gcd，xgcd

1.1.4 gmpy2模块

1.1.5 Crypto.Util模块

1.1.5.1 bytes_to_long

字节类型转为10进制

>>> from Crypto.Util.number import *
>>> bytes_to_long(b"flag")
1718378855

1.1.5.2 long_to_bytes

10进制转为字节类型

>>> from Crypto.Util.number import *
>>> long_to_bytes("1718378855")
b'flag'

1.1.5.3 getPrime

1.1.6 random模块

1.2 基础运算掌握

1.2.1 进制转化

16进制与字符串互转

python2下：
>>> b'user'.encode('hex')    #字符串转为16进制
'75736572'
>>> '75736572'.decode('hex')    #16进制转为字符串
'user'
-----------------------------------------------------------------------------------------
python3下：
''.join([hex(ord(c)).replace('0x','') for c in "user"])    #字符串转为16进制

>>> import binascii
>>> binascii.unhexlify('75736572').decode('utf8')    #16进制转为字符串
-----------------------------------------------------------------------------------------
bytearray类型互转
python3下：
>>> bytes.fromhex('deadbeef')
b'\xde\xad\xbe\xef'    #字符串转为16进制
>>> b'\xde\xad\xbe\xef'.hex()    
'deadbeef'    #16进制转为字符串

16进制与10进制互转

python2下：
>>> int(0xccccccccc)
54975581388L
>>> hex(54975581388)
'0xcccccccccL'
-----------------------------------------------------------------------------------------
python3下：
>>> int("66",16)
102
>>> hex(102)
'0x66'

1.3 数论知识

1.3.1 离散对数

构造公钥算法

参考资料：

1、数论简介以及公钥密码 https://wenku.baidu.com/view/fa4370ccb42acfc789eb172ded630b1c58ee9b00.html

1.4 密码学知识

1.4.1 密码类型

参考资料：

1、CTF——常见密码 https://blog.csdn.net/vhkjhwbs/article/details/99692399

1.4.1.1 曼彻斯特编码

参考资料：

1、差分曼彻斯特编码 https://baike.baidu.com/item/%E5%B7%AE%E5%88%86%E6%9B%BC%E5%BD%BB%E6%96%AF%E7%89%B9%E7%BC%96%E7%A0%81/7486879?fr=aladdin

2、曼彻斯特编码 https://baike.baidu.com/item/%E6%9B%BC%E5%BD%BB%E6%96%AF%E7%89%B9%E7%BC%96%E7%A0%81/8902319?fr=aladdin

1.4.1.2 仿射密码

参考资料：

1、信息安全–仿射密码 https://www.cnblogs.com/zishu/p/8650214.html

1.4.1.3 AES

1.5 工具

1.5.1 website

1、进制转化：https://tool.lu/hexconvert/

2、仿射密码解密：https://blog.csdn.net/x_yhy/article/details/83756908

1.5.2 sage

参考资料：

1、mirror of SageMath http://mirror.hust.edu.cn/sagemath/win/index.html

2、SageMath折腾笔记 https://www.jianshu.com/p/11030ad97edd

3、使用SageMath https://www.jianshu.com/p/ddf9376334cd

4、github下的项目 https://github.com/sagemath

2. crypto进阶

2.1 crypto_type

2.1.1 LFSR

参考资料：

1、深入分析CTF中的LFSR类题目（一） https://www.anquanke.com/post/id/181811

3. 真题

3.1 easy_prime（2020HK）

参考资料：

1、Compute the modular inverse using Extended GCD https://takp.me/posts/compute-the-modular-inverse-using-extended-gcd/

2、writeup：https://docs.qq.com/doc/DWnZCcG1tRENLc2ZJ?ADUIN=760244369&ADSESSION=1588816399&ADTAG=CLIENT.QQ.5689_.0&ADPUBNO=26982&jumpuin=760244369

3、 http://anh.cs.luc.edu/331/code/xgcd.py

题目源码：

# -*-coding:utf-8-*-
import gmpy
import binascii
from flag import generateN,flag

assert(flag[:7] == "l3hsec{")
assert(flag[-1] == "}")
ns = generateN()
cs = [0]*4
for i in range(4):
    tmp = flag[i*6:i*6+6]
  #六位六位的取
    tmp = int(binascii.hexlify(tmp), 16)
  #转化为10进制
    assert(cs[i] == pow(tmp, ns[i], ns[i]))
    cs.append(pow(tmp,ns[i],ns[i]))
f = open("output.txt")
f.write(ns,cs)
f.close()

发现任何两数之间gcd为质数，而且每个数恰好可以分解为4个质数，其中3个分别为与另外三个数的gcd。

#coding:utf-8
from binascii import unhexlify
from math import gcd
def xgcd(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    x0, x1, y0, y1 = 0, 1, 1, 0
    while a != 0:
        q, b, a = b // a, a, b % a
        y0, y1 = y1, y0 - q * y1
        x0, x1 = x1, x0 - q * x1
    return b, x0, y0  
ns = [953132552494206303012348408786397717024120659325268233076680572604098697916168653385278329626313598614575680244228262381838389535120393085942673903070279570977485804095602878303285246022965401,928899805423663693755492479177957865905961060276268728972280982039567441748465598294920208045639197902961091811958507823621118746074321384648224862021550115947173362257238535782360979512361361,1895738273463929341726412801769343217490103177236215681995039530128910586382946463987512006062214032212349782024052291872703750294681228486109434492925512597572002557806018748292562823816843093,1448313587366097491833529009986157413051969214099716038535604941172227859771995540645489672258057853586671280309005918618953394042015498627203762570380266032321857607975754833498540829298169607]
cs = [118970773770344149378137341138460281980614648083634897295967396676206557791102621552814126443049906530099386964179536465419908480994368590471625018267397766213154343646841600359013258748442316,238145257463910641951794768672569246985352083467488967568898082691705991421406969804917855770249818513742336674371599634613178449130135856057919373672907551727301704055321750764127345574615552, 657389389929881515388804420340482663287459042406748890285487483823807180002929633118827932943572291652551479200658771932105578947351729394654311493345963189287566901642275715408746374413837177,301848095091025953366454273747079605738957961883101530616601599039001385197654325158243724195165713204983805206548426107367727947468939581279543279719269482191430165339268214674606485978855583]
p = [gcd(ns[0], ns[1]), gcd(ns[0], ns[2]), gcd(ns[0], ns[3]), gcd(ns[1], ns[2]), gcd(ns[1], ns[3]), gcd(ns[2], ns[3])]
# print(p)
fac = [
 [p[0], p[1], p[2], ns[0]//(p[0]*p[1]*p[2])],
 [p[0], p[3], p[4], ns[1]//(p[0]*p[3]*p[4])],
 [p[1], p[3], p[5], ns[2]//(p[1]*p[3]*p[5])],
 [p[2], p[4], p[5], ns[3]//(p[2]*p[4]*p[5])],]
for i in range(4):
    a, b, c, d = fac[i]
    print(fac[i])
    x = xgcd(a*b*c*d-(a-1)*(b-1)*(c-1)*(d-1), (a-1)*(b-1)*(c-1)*(d-1))[1]
    print(x)
    print(unhexlify(hex(pow(cs[i], x, ns[i]))[2:])) #l3hsec{Pr1me_i5_50_fun!}

3.2 gm（2020HF）

其实只是知道了这个是挺标准的GM加密
然后谷歌找了半天资料，最后找到了一个简单的脚本：

https://github.com/ctfs/write-ups-2015/tree/master/asis-quals-ctf-2015/crypto/golden-metal
简单地算一下p和q的值，一套就出来了，大佬tql

参考资料：

1、原题：https://ctftime.org/writeup/16120

2、writeup：https://mi1itray_axe.gitee.io/2020/04/20/GM-crypto-system/

import sympy
from Crypto.Util.number import *

final_content = []
with open('output') as e:
    content = e.read()
    list_content = content.split(',')
    for i in list_content:
        # print(i.replace(']','').replace('[',''))
        final_content.append(i.replace(']','').replace('[','').replace("'",'').replace(" ",'').replace("L",'').replace("\n",''))

n=9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990905528141072864168544519279897224494849206184262202130305820187569148057247731243651084258194009459936702909655448969693589800987266378249891157940262898554047247605049549997783511107373248462587318323152524969684724690316918761387154882496367769626921299091688377118938693074486325995308403232228282839975697
phi=9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990711180904598841255660443214091848674376245163953774717113246203928244509033734184913005865837620134831142880711832256634797590773413831659733615722574830257496801417760337073484838170554497953033487131634973371143357507027731899402777169516770264218656483487045393156894832885628843858316679793205572348688820

p = sympy.symbols('p')
q = sympy.symbols('q')
res = sympy.solve([p*q-n, p+q-(n-phi+1)], (p, q))
#print (res)#这里得到下面的p，q

p=100216711979082556377200124903474313599976321274816484378304672662900171906266478070844182716079881540999761528986068197079878654411887736955737660906283803174161740862819849415729979371880583995409044839777513091451849412985192528374337852907661670174530234397743068706607004213367391908429077794527921775907
q=94130524494940356506875940901901506872984699033610928814269310978003376307730580667234209640309443564560267414630644861712331559440658853201804556781784493376284446426393074882942957446869925558422146677774085449915333876201669456003375126689843738090285370245240893337253184644114745083294361228182569510971

d=final_content

e = ((p-1)*(q-1)+4)//8
m = ""
for x in d:
  k = pow(int(x), e, p*q)
  # print(pow(k, 2, p*q))
  # print(x)
  if pow(k, 2, p*q) == int(x):
        #因为是读文件出来的x，都是字符串，所有要int转为整数，不然整数和字符串不相等，就出现问题了。
    m += "0"
  else:
    m += "1"
# print (m)
m=int(m,2)
print(long_to_bytes(m))

3.3 you_raise_me_up（2020网鼎杯青龙组）

考点：离散对数

题目源码：

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
import random

n = 2 ** 512
m = random.randint(2, n-1) | 1
c = pow(m, bytes_to_long(flag), n)
print 'm = ' + str(m)
print 'c = ' + str(c)

# m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
# c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499

解法1：

离散对数问题，直接用sage求解，脚本如下：

m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
n = 2**512
m = Mod(m,n)
c = Mod(c,n)
flag=discrete_log(c,m)
# flag = 56006392793405651552924479293096841126763872290794186417054288110043102953612574215902230811593957757
print(long_to_bytes(flag))
# flag{5f95ca93-1594-762d-ed0b-a9139692cb4a}

解法2：

from Crypto.Util.number import *
m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
n = 2
phi = 1
flag = [0, 1]
for i in range(2, 513):
    n *= 2
    phi *= 2
    candidate = []
    for i in flag:
        if pow(m, i, n) == c % n:
            candidate.append(i)
    flag = [x + phi for x in candidate] + candidate
for i in flag:
    print(long_to_bytes(i))

3.4 easy_crypto（2020HK）

做这道题的原因是想学习下java语言，开搞！！

参考资料：

1、java基础-BigInteger的使用 https://blog.csdn.net/suyebiubiu/article/details/78511556

import java.math.BigInteger;
import java.util.Random;

public class crypto
{
    static BigInteger e = new BigInteger("114514");
    //直接将十进制的字符串格式变成大整数
    static BigInteger p = new BigInteger("486782758980265419106566437773662434821707849903209898358740381800342941420169184139234071329598394271286443155137316343275438967772601578029350778343911038446374408250");
    static BigInteger h = new BigInteger("197285815436451554701121357540207727760367215453670717073481761209255345336604283966933286154040618892010511454547717773622062607956598784296775952923998110257788108099");

    static String table = new String("0123456789abcdefghijklnmopqrstuvwxyz");

    public static String Enc(String plaintext)
    {
        BigInteger[] cipher = new BigInteger[2];
        plaintext = plaintext.toLowerCase();
        BigInteger r = new BigInteger(new Random().nextInt(10000000)+"");
        String rtext = r.toString();
        System.out.println(rtext);
        int rlen = rtext.length();
        String text = "";
        for(int i = 0; i < plaintext.length(); i++)
        {
            int j = i % rlen;
            text += table.charAt((table.indexOf(plaintext.charAt(i))+Character.getNumericValue(rtext.charAt(j))) % 36);
            System.out.println(text);
        }
        BigInteger bText = new BigInteger(text, 36);
        cipher[0] = e.modPow(r, p);
        cipher[1] = h.modPow(r, p).multiply(bText);
        return cipher[0].toString(36)+"||"+cipher[1].toString(36);
    }

    public static void main(String[] args) throws Exception
    {
        System.out.println("Welcome to l3hsec, here is the flag:");
        String str1 = "This is the flag";
        String str2 = Enc(str1); // d4e03ge7tgvd3okpxq1l83w65q7vs55iwcav9ftehw9xtgfkn3oc3ofl2b52c6yjzl0jkn4xl83joqxlq023sacnpeddvq46709bz8kye1da||2h1oufyowds4axcoim3trm3kqm2hwlgbnrnblznktu4960o7hek0n9xgm9h1qfqq5w9k2i8wifbqv22c1mg8a79vwf8z6ydddbghvy3qzyq6jprbsjcv4o3ftwk5nmi
    }
}

3.5 easy_ya（2020网鼎杯青龙组）

参考资料：

1、https://badmonkey.site/archives/wangdingcup-2020.html

题目源码：

from secret import flag,key
from random import randint
from libnum import n2s,s2n
from Crypto.Util.number import getPrime
limit = lambda n: n & 0xffffffff
padding="\xe6\xe6\xe7\xe6\xe5\xe6\xe5\xe9\xe5"
ek='\xe6\x84\xbf'

def encode(key,data):
    pad  = randint(0x10000000,0xffffffff)
    Key  = [ord(i) for i in key]
    Data = [ord(i) for i in data]
    a = limit((Key[0] << 24) | (Key[1] << 16) | (Key[2] << 8) | Key[3])
    b = limit((Key[4] << 24) | (Key[5] << 16) | (Key[6] << 8) | Key[7])
    c = limit((Key[8] << 24) | (Key[9] << 16) | (Key[10] << 8) | Key[11])
    d = limit((Key[12] << 24) | (Key[13] << 16) | (Key[14] << 8) | Key[15])
    y = limit((Data[0] << 24) | (Data[1] << 16) | (Data[2] << 8) | Data[3])
    z = limit((Data[4] << 24) | (Data[5] << 16) | (Data[6] << 8) | Data[7])
    pads = 0
    for j in range(32):
        pads = limit(pads + pad)
        y = limit( y + ((z*16 + a) ^ (z + pads) ^ ((z>>5) + b)))
        z = limit( z + ((y*16 + c) ^ (y + pads) ^ ((y>>5) + d)))
    print hex((y << 52) ^ (pads << 20) ^ z)

#pow_check()
#token_check()

flag=flag.ljust(len(flag)+(-len(flag)&7),'\x00')
for i in range(0,len(flag)/8):
    encode(key,flag[8*i:8*i+8])

for i in range(9):
    ek+=padding[i] + key[2*i:2*i+2]

p=getPrime(2048)
e=0x10001

for i in range(2):
    q=getPrime(2048)
    n=p*q
    print n
    print pow(s2n(ek),e,n)

4. study

数论学习 https://peonycsa.com/mathjax-in-hexo/

CTF密码学方法总结 https://qsang.xin/2019/04/25/CTF%E5%AF%86%E7%A0%81%E5%AD%A6%E6%80%BB%E7%BB%93/

https://veritas501.space/2017/03/01/%E5%AF%86%E7%A0%81%E5%AD%A6%E7%AC%94%E8%AE%B0/#more