Crypto学习笔记(长期更新)

发布于 2023-11-15  243 次阅读


Crypto太难了😥,各种函数和公式,高数课得认真听了o( ̄┰ ̄*)ゞ ——————沃兹基

一. 现代密码

1.1 RSA

简介

RSA为一种非对称加密,在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 算法的可靠性由极大整数因数分解的难度决定。换言之,对一极大整数做因数分解愈困难,RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话,那么用 RSA 加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。如今,只有短的 RSA 密钥才可能被强力方式解破。到 2017 年为止,还没有任何可靠的攻击 RSA 算法的方式。

加密原理

RSA使用一对私钥和公钥。发送方通过公钥将数据加密并发送出去,接收方接收数据后使用私钥进行解密。公钥是公开的,私钥是个人才知道的(非对称加密)

加解密方法

RSA加密其中一个核心是欧拉函数:φ(n) = (p-1) * (q-1)。

其破解难度来源于P和Q两个质数,若P和Q设置的非常大,φ(n)和n也会变得非常大,即使公开n,也非常难以找到P和Q

RSA加密:

  1. 选择质数: 选择两个大质数,通常称为p和q。
  1. 计算乘积: 计算p和q的乘积,得到n。 n = p * q。
  2. 计算欧拉函数: 计算n的欧拉函数φ(n)。对于两个质数的乘积,φ(n) = (p-1) * (q-1)。
  3. 选择公钥: 选择一个与φ(n)互质的整数e,(这个数字通常是65537。

公钥的要求: 1.质数; 2. 1<e< φ(n) ; 3. 不是φ(n) 的因子

  1. 计算私钥: 计算e的模反元素d,使得(e * d) % φ(n) = 1。
  2. 生成公钥和私钥: 公钥是(n, e),私钥是(n, d)。
  3. 加密消息: 将要加密的消息转换为数字m,满足0 < m < n。计算c = m^e % n。
  4. 发送密文: 发送密文c,即加密后的消息。

个人理解

  1. 准备两个大的质数: 我们称之为p和q。比如2和7
  2. 把它们相乘: 把这两个大数字相乘,得到一个更大的数字n。n=p*q=2*7=14
  3. 计算欧拉函数:φ(n) = (p-1) * (q-1)。φ(n)=(2-1)*(7-1)=6
  4. 选公钥: 找到一个数字e,它和(p-1) * (q-1)没有公共因数(除了1以外没有其他相同的因数)。e=5
  5. 生成公钥: 公钥是(n, e)。 公钥是(14,5)
  6. 找到一个与e关联的数字d: 找到一个数字d,使得(e * d)除以(p-1) * (q-1)的余数等于1。
  7. 生成私钥: 私钥是(n, d)。
  8. 加密消息: 把要发送的消息转换成一个数字m,确保m比n小。然后用公钥对m进行加密,得到一个加密后的数字c。明文m^e%n=密文c

RSA解密:

  1. 接收密文: 接收密文c。
  2. 使用私钥: 使用私钥(n, d)。计算m = c^d % n。---- 密文c^d%n=明文m
  3. 得到原文: m即为解密后的原文。

个人理解

由于这个加密是通过求余来进行的,所以私钥和公钥在进行运算后是可以得到相同的明文的

攻击方法

相关题目

RSA

在一次RSA密钥对生成中,假设p=473398607161,q=4511491,e=17

求解出d作为flag提交

从题目中了解到p和q,可以写一个程序直接出答案

def mod_inverse(a, m):
    """计算模反元素"""
    m0, x0, x1 = m, 0, 1
    while a > 1:
        q = a // m
        m, a = a % m, m
        x0, x1 = x1 - q * x0, x0
    return x1 + m0 if x1 < 0 else x1

def calculate_d(p, q, e):
    """计算 RSA 私钥 d"""
    phi_n = (p - 1) * (q - 1)
    d = mod_inverse(e, phi_n)
    return d

p = int(input("请输入 p 的值: "))
q = int(input("请输入 q 的值: "))
e = int(input("请输入 e 的值: "))

d = calculate_d(p, q, e)
print("计算得到的私钥 d:", d)

RSA1

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229

q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469

dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929

dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041

c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

c是给定的密文,要求我们进行解密。

知道了p和q,我们可以将公钥和私钥的n以及私钥的d求出来。这道题我犯了一个错误,误以为dp是d*p,做不出来题目后去查了一下才知道在RSA中,dp并不是简单地d×q的意思。在RSA算法中,dp是私钥dp−1模的结果。

这题我们可以在python中通过inverse处理模逆

from Crypto.Util.number import inverse

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

n = p * q
phi_n = (p - 1) * (q - 1)

q_inv = inverse(q, p)
p_inv = inverse(p, q)
d = (dp * q * q_inv + dq * p * p_inv) % phi_n

m = pow(c, d, n)

print("解密后的消息:", m)

1.2 背包加密

相关数学名词

背包加密算法有一些数学名词需要理解。以下是一些主要的数学名词及其解释:

  1. 超递归子集和: 超递归子集和是指集合中的元素之和对于任何子集都是唯一的。在背包加密中,这个集合中的元素是由算法生成的,作为私钥的一部分。超递归子集和的唯一性是算法的关键。
  2. 整数乘法因子: 在背包加密中,整数乘法因子是一个随机选择的整数,用于构建公钥。这个因子与超递归子集和中的每个元素相乘,得到公钥的元素。
  3. 加权求和: 在加密过程中,要加密的消息会被转换成一个二进制位串。加权求和是将这个二进制位串与公钥中的元素相乘,并将结果相加的过程。这一步骤产生了加密后的密文。
  4. 背包问题: 背包问题是一个组合优化问题,涉及将一组物品放入背包中,使得它们的总价值最大,但不能超过背包的容量。在背包加密中,通过构造一个具有特定性质的超递归子集和,可以将加密问题转化为一个背包问题,从而增加了算法的安全性。
  5. 逆模运算: 在解密过程中,使用逆模运算来还原加密后的二进制位串。逆模运算是模运算的逆运算,通常用于找到整数的乘法逆元。

密钥生成

  1. 生成一个超递归子集和,确保它是超递归的,即任何子集的和都是唯一的。
  2. 随机选择一个整数乘法因子。
  3. 计算公钥:将超递归子集和中的每个元素都乘以整数乘法因子。

加密

  1. 将要加密的消息转换为二进制位串。
  2. 使用公钥对位串进行加权求和。

解密

  1. 使用私钥的超递归子集和和整数乘法因子,找到一个可解的背包问题。
  2. 使用解决背包问题的方法还原加密后的二进制位串。

注意事项

  • 超递归子集和的选择: 超递归子集和必须满足一定条件,以确保加密的安全性。
  • 对加密强度的考虑: 背包加密对于密钥的选择和超递归子集和的生成都有很高的要求,不当的选择可能导致被攻破。

示例代码 (不会写,由GPT生成)

以下是一个简单的Python示例代码,演示了背包加密的密钥生成、加密和解密过程。

import random

def generate_key(length):
    superincreasing_set = [random.randint(1, 100) for _ in range(length)]
    multiplier = random.randint(max(superincreasing_set), 2**length)
    public_key = [element * multiplier for element in superincreasing_set]
    private_key = superincreasing_set
    return public_key, private_key

def encrypt(message, public_key):
    binary_message = ''.join(format(ord(char), '08b') for char in message)
    ciphertext = sum(int(binary_message[i]) * public_key[i] for i in range(len(public_key)))
    return ciphertext

def decrypt(ciphertext, private_key, multiplier):
    subset_sum = sum(private_key)
    inverse_modulo = pow(multiplier, -1, subset_sum)
    decrypted_binary = ''
    for element in reversed(private_key):
        if ciphertext >= element:
            decrypted_binary += '1'
            ciphertext -= element
        else:
            decrypted_binary += '0'
    decrypted_message = ''.join(chr(int(decrypted_binary[i:i+8], 2)) for i in range(0, len(decrypted_binary), 8))
    return decrypted_message

# 示例用法
public_key, private_key = generate_key(8)
print("Public Key:", public_key)
print("Private Key:", private_key)

message = "Hello, Knapsack Cryptosystem!"
ciphertext = encrypt(message, public_key)
print("Encrypted:", ciphertext)

decrypted_message = decrypt(ciphertext, private_key, public_key[0])
print("Decrypted:", decrypted_message)

二.古典密码

2.1 云影密码

原理

使用 0,1,2,4,8 四个数字,其中 0 用来表示间隔,其他数字以加法可以表示出 如:28=10,124=7,18=9,再用 1->26 表示 A->Z。

该密码有以下特点

  • 只有 0,1,2,4,8

解码脚本

(脚本是python的,我也不懂为啥显示cs)这可能是全网第一份云影密码的脚本,欢迎取用。

def decrypt_cloud_shadow_code(encoded_message):
    # 将数字映射到字母(1 -> A,2 -> B,...,26 -> Z)
    num_to_letter = {i: chr(64 + i) for i in range(1, 27)}

    # 使用'0'作为分隔符将消息分成组
    groups = encoded_message.split('0')

    # 解密每个组
    decrypted_message = ''
    for group in groups:
        if group:  # 检查组是否非空
            total = sum(int(digit) for digit in group)
            decrypted_message += num_to_letter.get(total, '?')  # 对于无效数字,使用'?'表示

    return decrypted_message

# 用户输入
user_input = input("输入加密的消息: ")
decrypted_message = decrypt_cloud_shadow_code(user_input)
print(f"解密后的消息: {decrypted_message}")

2.2 JSFuck

原理

JSFuck 可以只用 6 个字符 []()!+ 来编写 JavaScript 程序。比如我们想用 JSFuck 来实现 alert(1) 代码如下

[][(![]+[])[+[[+[]]]]+([][[]]+[])[+[[!+[]+!+[]+!+[]+!+[]+!+[]]]]+(![]+[])[+[[!+[]+!+[]]]]+(!![]+[])[+[[+[]]]]+(!![]+[])[+[[!+[]+!+[]+!+[]]]]+(!![]+[])[+[[+!+[]]]]][([][(![]+[])[+[[+[]]]]+([][[]]+[])[+[[!+[]+!+[]+!+[]+!+[]+!+[]]]]+(![]+[])[+[[!+[]+!+[]]]]+(!![]+[])[+[[+[]]]]+(!![]+[])[+[[!+[]+!+[]+!+[]]]]+(!![]+[])[+[[+!+[]]]]]+[])[+[[!+[]+!+[]+!+[]]]]+([][(![]+[])[+[[+[]]]]+([][[]]+[])[+[[!+[]+!+[]+!+[]+!+[]+!+[]]]]+(![]+[])[+[[!+[]+!+[]]]]+(!![]+[])[+[[+[]]]]+(!![]+[])[+[[!+[]+!+[]+!+[]]]]+(!![]+[])[+[[+!+[]]]]]+[])[+[[!+[]+!+[]+!+[]+!+[]+!+[]+!+[]]]]+([][[]]+[])[+[[+!+[]]]]+(![]+[])[+[[!+[]+!+[]+!+[]]]]+(!![]+[])[+[[+[]]]]+(!![]+[])[+[[+!+[]]]]+([][[]]+[])[+[[+[]]]]+([][(![]+[])[+[[+[]]]]+([][[]]+[])[+[[!+[]+!+[]+!+[]+!+[]+!+[]]]]+(![]+[])[+[[!+[]+!+[]]]]+(!![]+[])[+[[+[]]]]+(!![]+[])[+[[!+[]+!+[]+!+[]]]]+(!![]+[])[+[[+!+[]]]]]+[])[+[[!+[]+!+[]+!+[]]]]+(!![]+[])[+[[+[]]]]+([][(![]+[])[+[[+[]]]]+([][[]]+[])[+[[!+[]+!+[]+!+[]+!+[]+!+[]]]]+(![]+[])[+[[!+[]+!+[]]]]+(!![]+[])[+[[+[]]]]+(!![]+[])[+[[!+[]+!+[]+!+[]]]]+(!![]+[])[+[[+!+[]]]]]+[])[+[[!+[]+!+[]+!+[]+!+[]+!+[]+!+[]]]]+(!![]+[])[+[[+!+[]]]]]((![]+[])[+[[+!+[]]]]+(![]+[])[+[[!+[]+!+[]]]]+(!![]+[])[+[[!+[]+!+[]+!+[]]]]+(!![]+[])[+[[+!+[]]]]+(!![]+[])[+[[+[]]]]+([][(![]+[])[+[[+[]]]]+([][[]]+[])[+[[!+[]+!+[]+!+[]+!+[]+!+[]]]]+(![]+[])[+[[!+[]+!+[]]]]+(!![]+[])[+[[+[]]]]+(!![]+[])[+[[!+[]+!+[]+!+[]]]]+(!![]+[])[+[[+!+[]]]]]+[])[+[[+!+[]]]+[[!+[]+!+[]+!+[]+!+[]+!+[]]]]+[+!+[]]+([][(![]+[])[+[[+[]]]]+([][[]]+[])[+[[!+[]+!+[]+!+[]+!+[]+!+[]]]]+(![]+[])[+[[!+[]+!+[]]]]+(!![]+[])[+[[+[]]]]+(!![]+[])[+[[!+[]+!+[]+!+[]]]]+(!![]+[])[+[[+!+[]]]]]+[])[+[[+!+[]]]+[[!+[]+!+[]+!+[]+!+[]+!+[]+!+[]]]])()

其他一些基本的表达:

false       =>  ![]
true        =>  !![]
undefined   =>  [][[]]
NaN         =>  +[![]]
0           =>  +[]
1           =>  +!+[]
2           =>  !+[]+!+[]
10          =>  [+!+[]]+[+[]]
Array       =>  []
Number      =>  +[]
String      =>  []+[]
Boolean     =>  ![]
Function    =>  []["filter"]
eval        =>  []["filter"]["constructor"]( CODE )()
window      =>  []["filter"]["constructor"]("return this")()

工具

2.3 BrainFuck

原理

Brainfuck,是一种极小化的计算机语言,它是由 Urban Müller 在 1993 年创建的。我们举一个例子,如果我们想要一个在屏幕上打印 Hello World!,那么对应的程序如下。对于其中的原理,感兴趣的可以自行网上搜索。

++++++++++[>+++++++>++++++++++>+++>+<<<<-]
++.>+.+++++++..+++.>++.<<+++++++++++++++.
.+++.------.--------.>+.>.

与其对应的还有 ook。

工具

2.4 键盘密码

键盘密码采用手机键盘或者电脑键盘进行加密。

手机键盘密码

手机键盘加密方式,是每个数字键上有 3-4 个字母,用两位数字来表示字母,例如:ru 用手机键盘表示就是:7382,那么这里就可以知道了,手机键盘加密方式不可能用 1 开头,第二位数字不可能超过 4,解密的时候参考此

关于手机键盘加密还有另一种方式,就是「音的」式(这一点可能根据手机的不同会有所不同),具体参照手机键盘来打,例如:「数字」表示出来就是:748 94。在手机键盘上面按下这几个数,就会出:「数字」的拼音。

电脑键盘棋盘

电脑键盘棋盘加密,利用了电脑的棋盘方阵。

电脑键盘坐标

电脑键盘坐标加密,利用键盘上面的字母行和数字行来加密,例:bye 用电脑键盘 XY 表示就是:351613

电脑键盘 QWE

电脑键盘 QWE 加密法,就是用字母表替换键盘上面的排列顺序。

键盘布局加密

简单地说就是根据给定的字符在键盘上的样子来进行加密。

2.5 培根密码

原理

培根密码使用两种不同的字体,代表 A 和 B,结合加密表进行加解密。

aAAAAAgAABBAnABBAAtBAABA
bAAAABhAABBBoABBABu-vBAABB
cAAABAi-jABAAApABBBAwBABAA
dAAABBkABAABqABBBBxBABAB
eAABAAlABABArBAAAAyBABBA
fAABABmABABBsBAAABzBABBB

上面的是常用的加密表。还有另外的一种加密表,可认为是将 26 个字母从 0 到 25 排序,以二进制表示,A 代表 0,B 代表 1。

下面这一段内容就是明文 steganography 加密后的内容,正常字体是 A,粗体是 B:

To encode a message each letter of the plaintext is replaced by a group of five of the letters'A' or 'B'.

可以看到,培根密码主要有以下特点

  • 只有两种字符
  • 每一段的长度为 5
  • 加密内容会有特殊的字体之分,亦或者大小写之分。

工具

三. 我也不知道该怎么分

中文电码

中文电码,又称中文商用电码中文电报码中文电报明码,原本是于电报之中传送中文信息的方法。它是第一个把汉字化作电子讯号的编码表。

摩尔斯电码在1835年发明后,一直只能用来传送英语或以拉丁字母拼写的文字。1873年,法国驻华人员威基杰(Septime Auguste Viguier)参照《康熙字典》的部首排列方法,挑选了常用汉字6800多个,编成了第一部汉字电码本《电报新书》。后由郑观应将其改编成为《中国电报新编》。

中文电码表采用了四位阿拉伯数字作代号从0001到9999按四位数顺序排列用四位数字表示最多一万个汉字、字母和符号。汉字先按部首,后按笔划排列。字母和符号放到电码表的最尾。后来由于一万个汉字不足以应付户籍管理的要求,又有第二字面汉字的出现。在香港,两个字面都采用同一编码,由输入员人手动选择字面;在台湾,第二字面的汉字会在开首补上“1”字,变成5个数字的编码。


技术号