boxmoe_header_banner_img

困困小猫の秘密基地

加载中

文章导读

密码学基础(一)


avatar
kunkunxiaomao 2025年10月5日 92

前言

这里是之前写过的程序,并非是完整的密码学,所以只涉及到了一点点,可能不全。

古典密码之凯撒密码

1.1 历史背景

凯撒密码由古罗马的盖乌斯・尤利乌斯・凯撒(Gaius Julius Caesar)所创,他在军事通信中广泛使用该密码,通常采用偏移量k=3的方式,这也是 “凯撒移位” 这一名称的由来。例如,他会把命令中的字母按此规则转换,以防止敌方截获信息后轻易读懂。

1.2 安全性分析

由于凯撒密码只有 26 种可能的偏移情况,在现代计算机技术下,可通过暴力破解(即尝试所有 26 种偏移量)在极短时间内解密,所以它仅适用于对安全性要求极低的简单场景,不能用于保护敏感信息。

1.3 原理

凯撒密码又被称为凯撒变换或者叫变换密码。它是一种替换加密,通过将明文中的所有字母都在字母表上向后(或向前)移动固定的数目称为密文。

例如当偏移量为3时 ABCDEFGHIJKLMNOPQRSTUVWXYZ DEFGHIJKLMNOPQRSTUVWXYZABC

凯撒密码看似简单,但其不仅本身就是一种加密方式,也同样作为很多加密算法的重要过程。例如,凯撒密码通常作为维吉尼亚密码中的一个步骤。
如果将凯撒密码写成数字表达式,那么加密函数将为:
image
解密函数即为
image
其中,k为偏移量。可以发现该密码只有26种不同的可能,我们要解密只需要遍历所有的可能,找到有意义的一组字符串即可。

1.4 代码

对于上述的公式,我们可以利用python将其实现出来。对于这个加密解密方法我们只需要解决的一个问题是,比如当密钥是1时,Z怎么变成A,这是编程的关键。所以我们可以考虑
image
这样子相当于将字母A作为一开始的字母,在其基础上进行加减,变成其他字母。而ord(now)-ord(a)是告诉当前字母是第几个字母,加上其偏移量后进行模运算达到计算结果。
点击查看代码

#加密部分
def casar(text,k):
    result = ""
    for char in text:
        if char.isalpha():
            # 处理大写字母
            if char.isupper():
                result += chr((ord(char) - ord("A") + k) % 26 + ord("A"))
            # 处理小写字母
            else:
                result += chr((ord(char) - ord("a") + k) % 26 + ord("a"))
        else:
            # 非字母字符保持不变
            result += char
    return result

#解密部分
def casar_decrypt(text,k):
    result = ""
    for char in text:
        if char.isalpha():
            # 处理大写字母
            if char.isupper():
                result += chr((ord(char) - ord("A") - k) % 26 + ord("A"))
            # 处理小写字母
            else:
                result += chr((ord(char) - ord("a") - k) % 26 + ord("a"))
        else:
            # 非字母字符保持不变
            result += char
    return result

def casar_decrypt_no_k(text):
    for k in range(1,26):
        result = ""
        for char in text:
            if char.isalpha():
                # 处理大写字母
                if char.isupper():
                    result += chr((ord(char) - ord("A") - k) % 26 + ord("A"))
                # 处理小写字母
                else:
                    result += chr((ord(char) - ord("a") - k) % 26 + ord("a"))
            else:
                # 非字母字符保持不变
                result += char
        print(f"密钥 {k} 的解密结果: {result}")
    return

while True:
    print("1.加密")
    print("2.解密")
    print("3.解密无密钥")
    print("4.退出")
    choice = input("请输入你的选择:")
    if choice == "1":
        text = input("请输入要加密的文本:")
        k = int(input("请输入加密密钥:"))
        print("加密后的文本为:" + casar(text,k))
    elif choice == "2":
        text = input("请输入要解密的文本:")
        k = int(input("请输入解密密钥:"))
        print("解密后的文本为:" + casar_decrypt(text,k))
    elif choice == "3":
        text = input("请输入要解密的文本:")
        casar_decrypt_no_k(text)
    elif choice == "4":
        break
    else:
        print("请输入正确的选择!")

Atbash 密码

Atbash Cipher是一种简单的替换密码,与凯撒相类似,区别在于Atbash密码使用的一般是前后字母互换。例如:

  • ABCDEFGHIJKLMNOPQRSTUVWXYZ
  • ZYXWVUTSRQPONMLKJIHGFEDCBA
    同样的可以利用ASCII表转回进行解密或者词频分析进行破解。
    例题:wl blf pmld zgyzhs kzhhdliw
    对此进行写加密解密算法,只需要注意这里用的是ord(Z) – 当前字母的码值然后加上ord(A),于是可以依照此思路写出加密解密算法。

点击查看代码

#加密
def atbash(text):
    #ord(A) <--> ord(Z)
    #ord(B) <--> ord(Y)
    #0  <-->   25
    #1  <-->  24
    #ord(Z) - ord(X) + ord(A)
    result = ""
    for char in text:
        if char.isalpha():
            # 处理大写字母
            if char.isupper():
                result += chr(ord("Z") - ord(char) + ord("A"))
            # 处理小写字母
            else:
                result += chr(ord("z") - ord(char) + ord("a"))
        else:
            # 非字母字符保持不变
            result += char
    return result

#解密
def atbash_decrypt(text):
    return atbash(text)

while True:
    print("1.加密")
    print("2.解密")
    print("3.退出")
    choice = input("请输入你的选择:")
    if choice == "1":
        text = input("请输入要加密的文本:")
        print("加密后的文本为:" + atbash(text))
    elif choice == "2":
        text = input("请输入要解密的文本:")
        print("解密后的文本为:" + atbash_decrypt(text))
    elif choice == "3":
        break
    else:
        print("输入错误,请重新输入")

摩斯密码

摩斯密码又叫摩尔斯电码,是由美国人在1836年发明的一种通过时断,以及不同的排列顺序来表达不同英文字母、数字和标点符号的信息代码,主要由点、划、字符间的停顿、单词间的停顿和句子之间的停顿构成。
莫斯码表如下所示,用python字典进行展示。
点击查看代码

MOSS_PASSWORD = {'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': '--..',
                   '1': '.----', '2': '..---', '3': '...--',
                   '4': '....-', '5': '.....', '6': '-....',
                   '7': '--...', '8': '---..', '9': '----.',
                   '0': '-----', ', ': '--..--', '.': '.-.-.-',
                   '?': '..--..', '/': '-..-.', '-': '-....-',
                   '(': '-.--.', ')': '-.--.-'}

摩斯密码有时也会用01、AB等不同的符号表示。所以当我们观察到如果在一段语句中有着明显的间隔时,就需要考虑使用摩斯密码了。接下来将展示摩斯密码的编程。
点击查看代码

#创建密码本
MOSS_PASSWORD = {'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': '--..',
                   '1': '.----', '2': '..---', '3': '...--',
                   '4': '....-', '5': '.....', '6': '-....',
                   '7': '--...', '8': '---..', '9': '----.',
                   '0': '-----', ', ': '--..--', '.': '.-.-.-',
                   '?': '..--..', '/': '-..-.', '-': '-....-',
                   '(': '-.--.', ')': '-.--.-'}

MOSS_key={
    ".":'0',
    "-":'1'
}

#加密
def moss_encrypt(text):
    result = ""
    content = ""
    for char in text:
        if char.isalpha() or char in MOSS_PASSWORD.keys():
            result += MOSS_PASSWORD[char.upper()] + " "
        else:
            result += char
    return result

#解密
def moss_decrypt(text):
    result = ""
    for char in text.split():
        if char in MOSS_PASSWORD.values():
            result += list(MOSS_PASSWORD.keys())[list(MOSS_PASSWORD.values()).index(char)]
        else:
            result += char
    return result

while True:
    print("1.加密")
    print("2.解密")
    print("3.退出")
    choice = input("请输入你的选择:")
    if choice == "1":
        text = input("请输入要加密的文本:")
        print("加密后的文本为:" + moss_encrypt(text))
    elif choice == "2":
        text = input("请输入要解密的文本:")
        print("解密后的文本为:" + moss_decrypt(text))
    elif choice == "3":
        break
    else:
        print("输入错误,请重新输入")

仿射密码

数论

在正式介绍仿射密码之前,我们需要了解一些数论知识。为我们后面的学习有更好的基础。

1.1 数论的概念

这里我们主要说的是初等数论,其是数论的一个分支。一般说来,指用算术推导方法论证数论命题的分支学科。

1.2 算术基本定理

算术基本定理可表述为:任何一个大于1的自然数 N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积。即image
,这里image
均为质数,其中指数是正整数。这样的分解称为N 的标准分解式。
定理的应用:
一个大于1的正整数N,如果它的标准分解式为:image,那么它的正因数个数为image
它的全体正因数之和为
image
对于该定理我们可以使用python进行实现:
点击查看代码

def prime(n):
    factor = []
    for i in range(2,n+1):  # 从2开始遍历到n
        while n % i == 0:   # 如果n能被i整除
            factor.append(i)     # 把i加入因子列表
            n = n // i       # 把n除以i的商赋值给n
        if n == 1:
            break
    return factor


print(prime(30))

1.3 欧几里得算法

欧几里得算法又称辗转相除法,是指用于计算两个正整数a,b的最大公约数。计算公式为gcd(a,b) = gcd(b,a mod b)。
两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。
将其编写为python语言为:
点击查看代码

def gcd(m,n):
    if(m % n == 0):
        return n
    else:
        return gcd(n,m % n)

1.4 扩展欧几里得算法

除了计算a、b两个整数的最大公约数,此算法还能找到整数x、y(其中一个很可能是负数)。通常谈到最大公因子时,我们都会提到一个非常基本的事实: 给予二整数a与b,必存在有整数x与y使得ax+by=gcd(a,b)。有两个数a,b,对它们进行辗转相除法,可得它们的最大公约数——这是众所周知的。然后,收集辗转相除法中产生的式子,倒回去,可以得到ax+by=gcd(a,b)的整数解。
例:求5ximage1(mod 18)
image
扩展欧几里得算法可以用来计算模逆元,而模反元素在RSA加密算法中有很重要的地位。用代码实现:
点击查看代码

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

1.5 孙子定理

孙子定理是中国古代求解一次同余式组的方法。是数论中一个重要定理。又称中国剩余定理。
孙子定理是初等数论中的一个重要定理,凝结着中国古代数学家的智慧,在加密、秘密共享、数字签名等领域都有重要应用。
用现代数学的语言来说明的话,中国剩余定理给出了以下的一元线性同余方程组:
image
有解的判定条件,并用构造法给出了在有解情况下的具体形式。
中国剩余定理说明:假设整数image两两互质,则对任意的整数image,方程组(S)有解,并且通解可以为:
image
其中image
在此之前,我们需要了解几个知识点:

  • a mod b = (a+k*b) mod b
  • (a * k) mod b = k * (a mod b)
  • image的意思是a mod c = b mod c
    例:
    image
    image
    所以对于中国剩余定理,我们可以写出如下算法步骤:
    判断正整数m1,m2,…,mk是否两两互素,是,则继续;否则跳出;
    计算m = m1m2…mk,Mj = m / mj;
    计算image
    计算image
    计算image

点击查看代码

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

def crt(remainders, moduli):
    if len(remainders) != len(moduli):
        return None  # 余数和模数数量必须相等

    x = 0
    M = 1  # 所有模数的乘积

    # 步骤 1: 计算所有模数的乘积 M
    for m in moduli:
        M *= m

    # 步骤 2: 循环求解每一个同余方程,并累加结果
    for a_i, m_i in zip(remainders, moduli):
        # 计算 M_i = M / m_i
        M_i = M // m_i

        # 步骤 3: 使用扩展欧几里得算法求 M_i 模 m_i 的逆元 inv_i
        # 即求解方程: M_i * inv_i ≡ 1 (mod m_i)
        g, inv_i, _ = extended_gcd(M_i, m_i)

        if g != 1:
            # 如果 M_i 和 m_i 的最大公约数不为1,说明模数之间不互质,
            # 在这种情况下,方程组可能无解。
            # 更严谨的做法是检查 a_i % g 是否等于 a_j % g,此处简化处理。
            return None

        # 关键步骤:确保逆元是正数
        inv_i = inv_i % m_i

        # 步骤 4: 将当前方程的解累加
        # 解的形式为: a_i * M_i * inv_i
        x += a_i * M_i * inv_i

    # 步骤 5: 返回最小非负整数解
    return x % M    

1.6 费马小定理

如果p是一个质数,而整数a不是p的倍数,则有image
例如:计算image除以13的余数
image

仿射密码

仿射密码将字母表中每个字母对应的值使用一个简单的数学函数映射到对应的数值,再把数值转化为字母。同理因为是一个单射函数,所以它也是单表替换加密。
字母和数值对应关系为A、B、C、……、X、Y、Z对应0、1、2、……、23、24、25。
假设我们选择的函数为
image
则对应的解密函数为
image
这里的image即a在模26意义下的逆元。
用代码实现:
点击查看代码

#欧几里得算法
def gcd(a,b):
    if a == 0:
        return b,0,1
    else:
        gcd1,x,y = gcd(b%a,a)
        return gcd1,y - (b//a) * x,x


#加密
def affine_encrypt(text,a,b):
    result =""
    for char in text:
        if char.isalpha():
            # 计算加密后的字符:(a * (字母的数字表示) + b) % 26
            char_code = (a * (ord(char.upper()) - 65) + b) % 26
            result += chr(char_code + 65)
        else:
            result += char
    return result

#解密
def affine_decrypt(text,a,b):
    a_ni = gcd(a,26)[1]
    result =""
    for char in text:
        if char.isalpha():
            # 计算解密后的字符:a的逆元 * (字母的数字表示 - b) % 26
            char_code = (a_ni * ((ord(char.upper()) - 65) - b)) % 26
            result += chr(char_code + 65)
        else:
            result += char
    return result

while True:
    print("1.加密")
    print("2.解密")
    print("3.退出")
    choice = input("请输入你的选择:")
    if choice == "1":
        text = input("请输入要加密的文本:")
        a = int(input("请输入a的值:"))
        b = int(input("请输入b的值:"))
        print("加密后的文本为:" + affine_encrypt(text,a,b))
    elif choice == "2":
        text = input("请输入要解密的文本:")
        a = int(input("请输入a的值:"))
        b = int(input("请输入b的值:"))
        print("解密后的文本为:" + affine_decrypt(text,a,b))
    elif choice == "3":
        break
    else:
        print("输入错误,请重新输入")


评论(0)

查看评论列表

暂无评论


发表评论

表情 颜文字
插入代码

欢迎来到小站哦~

avatar

困困小猫

常年看番、打游戏,宅属性满分。不过偶尔也会出去玩啦 我在这里还是个新手,各位大佬来访还请轻一点喷~orz 欢迎光临! 还有一定要看隐私政策哦!!!

66
文章
4
评论
2
用户