就仿射密码(Affline)来一篇杂谈

admin 2022年12月4日20:36:26CTF专场评论27 views3950字阅读13分10秒阅读模式

0x00 前言

在密码学古典密码中,仿射密码无疑是单表代换加密中的典型。

在绝大多数单表代换加密中都有个通用特点,那就是在单表替换加密中,所有的加密方式几乎都有一个共性,那就是明密文一一对应。

所以说,一般有以下两种方式来进行破解

  • 在密钥空间较小的情况下,采用暴力破解方式

  • 在密文长度足够长的时候,使用词频分析,http://quipqiup.com/

而当密钥空间足够大的时候,且密文长度足够短的情况下,破解就变得较为困难。

0x01 相关知识简介

仿射密码是一种表单代换密码,字母表的每个字母相应的值使用一个简单的数学函数对应一个数值,再把对应数值转换成字母。

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

仿射密码的加密函数是 E(x)=(ax+b)(mod m),其中

  • x 表示明文按照某种编码得到的数字

  • a 和 m 互质

  • m 是编码系统中字母的数目(通常都是26)

解密函数是 D(x)=a−1(x−b)(mod m),其中 a^−1 是 a 在 Zm 群的乘法逆元。

所以对于仿射加密来说,要解密就要先求出a的逆元。

逆元的定义:群G中任意一个元素a,都在G中有唯一的逆元a^−1,具有性质aa^−1=a^−1a=e,其中e为群的单位元。

乘法逆元

模p意义下,一个数a如果有逆元x,那么除以a相当于乘以x。

在模n的意义下,a存在逆元的充要条件是n不等于1,且(a,n)互质。

def ModReverse(a,n):     if gcd == 1:        return (arr[0] % n + n) % n    else:        return -1

在满足存在逆元的条件(gcd==1,也就是互质)的情况下,返回(arr[0] % n + n) % n也就是返回了逆元。


0x02 相关样例演示

样例 1

下面我们以 E(x)=(5x+8)mod 26函数为例子进行介绍,加密字符串为 AFFINE CIPHER,这里我们直接采用字母表 26 个字母作为编码系统

就仿射密码(Affline)来一篇杂谈

其对应的加密结果是 IHHWVCSWFRCP

对于解密过程,正常解密者具有a与b,可以计算得到a^−1为 21,所以其解密函数是D(x)=21(x−8)(mod26),解密如下

就仿射密码(Affline)来一篇杂谈

可以看出其特点在于只有 26 个英文字母。

样例 2

这里我们已知加密函数为 y = 3x + 9,而加密之后的密文为:"JYYHWVPIDCOZ"

我们通过前面的基础知识简介可以知道它的加密函数是:  

  • y=ax+b(mod m),其中a和m互质,m是字母的数目。

解密函数是:x=a−1(y-b)(mod m),其中a^−1是a的数论倒数。

所以经过计算可以得出 a^−1= 9,也就是说解密函数可以描述为:y = 9*(x-9) (mod m),其中m为加密时的字母数,也就是26

下面进行层层计算演示:

密文 J Y Y H W V P I D C O Z
y 9 24 24 7 22 21 15 8 3 2 14 25
x = 9 * (y - 9) 0 135 135 -18 117 108 54 -9 -54 -72 45 144
x mod 26 0 5 5 8 13 4 2 17 24 15 19 14
明文 A F F I N E C R Y P T O

据此可以推出明文为:AFFINECRYPTO

以下贴出解码所需要的exp,也可以通过在线网站进行解码

# 改进欧几里得算法求线性方程的x与ydef get(a, b):    if b == 0:        return 1, 0    else:        k = a // b        remainder = a % b        x1, y1 = get(b, remainder)        x, y = y1, x1 - k * y1    return x, y

s = input("请输入解密字符:").upper()a = int(input("请输入a:"))b = int(input("请输入b:"))
# 求a关于26的乘法逆元x, y = get(a, 26)a1 = x % 26print("所求a的逆元为:", a1)
n = len(s)for i in range(n): cipher = a1 * (ord(s[i]) - 65 - b) % 26 res = chr(cipher + 65) print(res, end='')# AFFINECRYPTO


0x03 仿射变种-自定义密钥

近日在一道Cr题中遇到一个根据自定义密钥进行仿射加密的题,其在加密函数是 E(x)=(ax+b)(mod m)不变的情况下,更换加密所需的密钥而非正常情况下的26个英文字母,此时其解密函数仍是 D(x)=a^−1(x−b)(mod m),但已不可通过常规的解密网站或工具进行解密。接下来我们通过对例题进行逐步详解

加密脚本如下:


from Crypto.Util.number import *from flag import flagimport random
text = 'aCdhpnlmNKuRJbfVIXUvyTrSPqjBMzgwHZkAxWGiYetEsocDLFOQ'
def Affline_Encode(plain, a, b): cipher = '' for i in plain: if i not in text: cipher += i else: x = text.find(i) cipher += text[(x*a + b) % len(text)]
return cipher
while True: a=random.randint(1<<99, 1<<100) b=random.randint(1<<99, 1<<100) if GCD(a,52) == 1: break
assert flag[:6]=='DASCTF'print(Affline_Encode(flag, a, b))# cipher = 'CezmBh{BKDdD_oP_rKD_rdtF_cMHu}'

通过如上脚本可以看出其密钥为:aCdhpnlmNKuRJbfVIXUvyTrSPqjBMzgwHZkAxWGiYetEsocDLFOQ,长度为52,此时a的值便为0,而Q的值则为51。

而加密函数Affline_Encode即为仿射加密函数,其数式就是E(x)=(ax+b)(mod m)


# E(x)=(ax+b)(mod m)def Affline_Encode(plain, a, b): cipher = '' for i in plain:  if i not in text:   cipher += i  else:   x = text.find(i)   cipher += text[(x*a + b) % len(text)]
return cipher

而题中并没有给出系数a,b的值,CezmBh{BKDdD_oP_rKD_rdtF_cMHu}即为加密后的密文,此时我们可以根据已知的部分明文DASCTF和其所给出的加密函数来对a,b进行爆破,爆破a,b的函数部分如下:

def Get_Ab(S):    for a_ in range(len(text)):        for b_ in range(len(text)):            Cipher = encrypt(S, a_, b_)            for k in range(len(s)):                if Cipher == s[:6]:                    print(Cipher, a_, b_)                    break

运行可以得到爆破所得结果:

CezmBh 1 6CezmBh 27 32

如此可以看出a,b的取值有两组,再通过其解密函数:D(x)=a^−1(x−b)(modm)来对其进行解码而在本题中的密钥与常规题型有所不同,但本质上还是一致的,如此我们可以将解密函数定义如下:

# D(x)=a^−1(x−b)(mod m)def decrypt(m, _a, _b):    import gmpy2    for i_ in range(len(m)):        c = m[i_]        t = ((text.index(c) - _b) * gmpy2.invert(_a, len(text))) % len(text)        d = ''.join(text[t])        return d

其所返回的d也就是我们解码后的明文字符,如此我们即可解出

完整exp如下:

def encrypt(plain, a_, _b):    cipher = ''    for _i in plain:        if _i not in text:            cipher += _i        else:            x = text.find(_i)            cipher += text[(x * a_ + _b) % len(text)]    return cipher

def Get_Ab(S): for a_ in range(len(text)): for b_ in range(len(text)): Cipher = encrypt(S, a_, b_) for k in range(len(s)): if Cipher == s[:6]: print(Cipher, a_, b_) break

def decrypt(m, _a, _b): import gmpy2 for i_ in range(len(m)): c = m[i_] t = ((text.index(c) - _b) * gmpy2.invert(_a, len(text))) % len(text) d = ''.join(text[t]) return d

if __name__ == '__main__': text = 'aCdhpnlmNKuRJbfVIXUvyTrSPqjBMzgwHZkAxWGiYetEsocDLFOQ' # 自定义key,视题目情况进行修改 s = 'CezmBh{BKDdD_oP_rKD_rdtF_cMHu}' # 需要解密的字符串 Get_Ab('DASCTF') # 根据已知的部分密文获取a, b a, b = 27, 32 # 对非key的字符进行过滤,然后解码 for i in range(len(s)): if s[i] not in text: print(s[i], end="") else: print(decrypt(s[i], a, b), end="")# DASCTF{There_is_the_truE_fLag}

经测试第二组a,b即使本题所需的值。


0x04 写在最后

今天的简介就到这里啦,小编的水平有限,如有差误望各位大佬指正φ(* ̄0 ̄)


原文始发于微信公众号(7coinSec):就仿射密码(Affline)来一篇杂谈

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年12月4日20:36:26
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  就仿射密码(Affline)来一篇杂谈 http://cn-sec.com/archives/1444470.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: