↓Skip to main content

古典密码-仿射密码学习

·136 words
CTF
Yalois
Author
Yalois
freedom
Table of Contents

仿射密码（Affine Cipher）是一种古老的单字母替换密码，属于经典密码学范畴。

加密
#

$$ E(x) = (a\cdot x + b) \mod{m} $$

  • E(x)是加密后的字符的数值
  • x是明文字符的数值，通常是字母表的位置(A=0,B=1,…,Z=25)
  • a和b是密钥，而且a必须和m互质(在字母表中，通常m=26)
  • m是字符集的大小(对于英文字母，m=26)

加密步骤：

  1. 将明文字符转换为数字。
  2. 使用E(x)公式进行加密。
  3. 将加密后的数字转换回字符。

解密
#

仿射密码的解密过程可以用以下公式表示： $$ D(y) = a^-1\cdot(y-b)\mod{m} $$

  • D(y)是解密后的字符的数值
  • y是加密后的字符串的数值
  • $a^-1$是a的模逆元素，满足$a\cdot a^-1 \equiv 1\mod{m}$
  • b是加密时使用的密钥
  • m是字符集的大小

解密步骤：

  1. 计算a的模逆元素$a^-1$
  2. 将加密字符转换为数字。
  3. 使用D(y)进行解密。
  4. 将解密后的数字转换回字符。

加密解密Py脚本(26个字母)
# 

#Affine Cipher (仿射密码)
from gmpy2 import invert
Htable="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
Ltable="abcdefghijklmnopqrstuvwxyz"

#求最大公约数（GCD，Greatest Common Divisor）
#辗转相除法
def gcd(a,b):
    #b=0时，整除了，即最大公约数
    while b:
        a,b=b,a%b #b是余数，赋值给a,下一轮继续求余数
    return a
#判断a是否和b互质
def are_coprime(a,b):
    #最大公约数是1，则互质
    return gcd(a,b)==1

def affine_encrypt(text,a,b,m):
    enc_text=""
    if are_coprime(a,m):
        for i in text:
            if 'A'<=i<='Z':
                enc_text+=Htable[(a*(Htable.index(i))+b)%m]
            elif 'a'<=i<='z':
                enc_text+=Ltable[(a*(Ltable.index(i))+b)%m]
            else:
                enc_text+=i
        return enc_text
    else:
        print("a和m不互质，无法加密")
def affine_decrypt(text,a,b,m):
    dec_text=""
    if are_coprime(a,m):
        #好吧...其实扩展欧几里得和求模逆元还没学明白，就直接用了gmpy2的
        a_inv = invert(a, m)
        print(a_inv)
        for i in text:
            if 'A'<=i<='Z':
                dec_text+=Htable[(a_inv * (Htable.index(i)-b) ) %m]
            elif 'a'<=i<='z':
                dec_text+=Ltable[(a_inv * (Ltable.index(i)-b) ) %m]
            else:
                dec_text+=i
        return dec_text
    else:
        print("a和m不互质，无法解密")
c = affine_encrypt("flag{aff1n3_encrp4y}",3,4,26)
print(f"密文：{c}")
m = affine_decrypt(c,3,4,26)
print(f"明文：{m}")