The Algorithms logo
算法
关于我们捐赠

维吉尼亚密码

R
P
LETTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def main() -> None:
    message = input("Enter message: ")
    key = input("Enter key [alphanumeric]: ")
    mode = input("Encrypt/Decrypt [e/d]: ")

    if mode.lower().startswith("e"):
        mode = "encrypt"
        translated = encrypt_message(key, message)
    elif mode.lower().startswith("d"):
        mode = "decrypt"
        translated = decrypt_message(key, message)

    print(f"\n{mode.title()}ed message:")
    print(translated)


def encrypt_message(key: str, message: str) -> str:
    """
    >>> encrypt_message('HDarji', 'This is Harshil Darji from Dharmaj.')
    'Akij ra Odrjqqs Gaisq muod Mphumrs.'
    """
    return translate_message(key, message, "encrypt")


def decrypt_message(key: str, message: str) -> str:
    """
    >>> decrypt_message('HDarji', 'Akij ra Odrjqqs Gaisq muod Mphumrs.')
    'This is Harshil Darji from Dharmaj.'
    """
    return translate_message(key, message, "decrypt")


def translate_message(key: str, message: str, mode: str) -> str:
    translated = []
    key_index = 0
    key = key.upper()

    for symbol in message:
        num = LETTERS.find(symbol.upper())
        if num != -1:
            if mode == "encrypt":
                num += LETTERS.find(key[key_index])
            elif mode == "decrypt":
                num -= LETTERS.find(key[key_index])

            num %= len(LETTERS)

            if symbol.isupper():
                translated.append(LETTERS[num])
            elif symbol.islower():
                translated.append(LETTERS[num].lower())

            key_index += 1
            if key_index == len(key):
                key_index = 0
        else:
            translated.append(symbol)
    return "".join(translated)


if __name__ == "__main__":
    main()
关于此算法

维吉尼亚密码是一种著名的玩具密码。它是由意大利密码学家吉奥瓦尼·巴蒂斯塔·贝拉索于 1553 年发明的,但几个世纪以来一直被认为是由 16 世纪法国密码学家布莱斯·德·维吉涅尔发明的,他在 1586 年设计了一种类似的密码。

它易于加密和解密,但同时,它也容易被拦截和破解。它是一种多字母替换密码,这意味着同一个字母可以被不同的字母替换,具体取决于密钥。密钥是一个重复的单词或短语,其长度与消息的长度匹配。然后使用密钥的字母来移动消息的字母。

对凯撒密码的改进

维吉尼亚密码是对凯撒密码的改进。凯撒密码使用单个字符作为密钥来移动消息。相反,维吉尼亚密码使用单词或短语作为密钥。这意味着消息中不同位置出现的相同字符将被移动不同的数量。这使得破解密码更加困难。

设置

  1. 选择你要使用的消息空间。在本例中,我们将使用英语的所有小写字母。但我们也可以使用 ASCII 字符。让我们将消息空间的大小表示为 $n$。在本例中,$n = 26$。
  2. 为消息空间中的每个字母分配一个数值。例如,$a=1, b=2, c=3$ 等等。
  3. 选择一个密钥。

加密

  1. 重复密钥以匹配消息的长度。例如,如果消息是 checktheking,密钥是 chess,则重复密钥以匹配消息的长度。现在密钥是 chesschessch
  2. 现在,使用密钥的字母来移动消息的字母。令 $a$ 为 $1$,$b$ 为 $2$,以此类推。然后,使用以下公式加密消息:$C_i = (V(M_i) + V(K_i)) \mod n$,其中 $C_i$ 是位置 $i$ 的加密字母,$V(M_i)$ 是位置 $i$ 的字母的数值,$V(K_i)$ 是位置 $i$ 的字母的数值,$n$ 是消息空间的大小。
消息 c h e c k t h e k i n g
3 8 5 3 11 20 8 5 11 9 14 7
密钥 c h e s s c h e s s c h
移位 3 8 5 19 19 3 8 5 19 19 3 8
密文 f p j q z w p j z z c p

因此,加密后的消息是 fpjqzwjpzzcp

解密

解密是加密的逆运算。它通过从密文值中减去移位值来完成。公式为 $M_i = L((C_i - V(K_i)) \mod n)$,其中所有内容的定义如上,$L$ 另外定义为将数值转换回字母的函数。

密文 f p j q z w p j z z c p
密钥 c h e s s c h e s s c h
移位 3 8 5 19 19 3 8 5 19 19 3 8
3 8 5 3 11 20 8 5 11 9 14 7
消息 c h e c k t h e k i n g

因此,解密后的消息是 checktheking,如预期。

复杂度分析

加密

加密是通过将移位值添加到消息值来完成的。因此,时间复杂度为 $O(n)$,其中 $n$ 是消息的长度。我们使用线性数据结构(如数组)来存储消息和密钥。因此,空间复杂度为 $O(n)$

解密

解密类似于加密(减法运算除外)。因此时间和空间复杂度与加密相同 - $O(n)$

密码分析和注意事项

  1. 这是一个玩具密码。它很容易破解。它不安全。
  2. 有几种密钥(长度)查找方法,例如
  3. 一旦找到密钥长度,就可以使用频率分析来找到密钥,从而破解密码。
  4. 因此,此密码不应用于加密任何重要数据。