Шифр Виженера. Разбор алгоритма на Python

Недавно захотелось вспомнить свое «шпионское» детство и хотя бы базово изучить разные методы шифрования. И первым выбор пал на шифр Виженера. Сам по себе он не является чрезвычайно сложным, но достаточно долго считался криптоустойчивым. Века эдак с XV и к самому XIX, пока некто Казиски полностью не взломал шифр.
Однако ограничим цитирование Википедии только описанием самого алгоритма.

Метод является усовершенствованным шифром Цезаря, где буквы смещались на определенную позицию.
Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига.

Допустим у нас есть некий алфавит, где каждой букве соответствуют цифры:

image

Тогда если буквы a-z соответствуют числам 0-25, то шифрование Виженера можно записать в виде формулы:

image

Расшифровка:

image

По сути нам больше ничего и не нужно кроме двух этих формул и мы можем приступить к реализации.

Тут хочу сказать, что я постарался реализовать алгоритм не проще и изящнее, а наиболее понятно и развернуто.
Собственно приступим-с.

Закодируем слова 'Hello world' с хитрым ключом 'key'.

Сначала необходимо создать словарь символов, которые будут участвовать в шифровании:
def form_dict():
    d = {}
    iter = 0
    for i in range(0,127):
        d[iter] = chr(i)
        iter = iter +1
    return d

Дальше необходимо сопоставить буквы в нашем слове с буквами в словаре и присвоить им соответствующие числовые индексы
def encode_val(word):
    list_code = []
    lent = len(word)
    d = form_dict() 

    for w in range(lent):
        for value in d:
            if word[w] == d[value]:
               list_code.append(value) 
    return list_code

И так мы закодировали наше слово и ключ и получили 2 списка индексов:
Value= [72, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100]
Key = [107, 101, 121]

Дальше мы сопоставляем индексы ключа с индексами нашего слова функцией full_encode():
def comparator(value, key):
    len_key = len(key)
    dic = {}
    iter = 0
    full = 0

    for i in value:
        dic[full] = [i,key[iter]]
        full = full + 1
        iter = iter +1
        if (iter >= len_key):
            iter = 0 
    return dic 

def full_encode(value, key):
    dic = comparator(value, key)
    print 'Compare full encode', dic
    lis = []
    d = form_dict()

    for v in dic:
        go = (dic[v][0]+dic[v][1]) % len(d)
        lis.append(go) 
    return lis

def decode_val(list_in):
    list_code = []
    lent = len(list_in)
    d = form_dict() 

    for i in range(lent):
        for value in d:
            if list_in[i] == value:
               list_code.append(d[value]) 
    return list_code

Получаем наш индексы шифра и переводим их в строку функцией decode_val():

{0: [72, 107], 1: [101, 101], 2: [108, 121], 3: [108, 107], 4: [111, 101], 5: [32, 121], 6: [119, 107], 7: [111, 101], 8: [114, 121], 9: [108, 107], 10: [100, 101]}

Индексы: [52, 75, 102, 88, 85, 26, 99, 85, 108, 88, 74]

Получаем закодированное суперсекретное послание: 4KfXUcUlXJ

Раскодировать же все это можно с помощью функции full_decode(), первым аргументом которой есть список числовых индексов шифра, а вторым — список индексов ключа:

def full_decode(value, key):
    dic = comparator(value, key)
    print 'Deshifre=', dic
    d = form_dict() 
    lis =[]

    for v in dic:
        go = (dic[v][0]-dic[v][1]+len(d)) % len(d)
        lis.append(go) 
    return lis


Все так же получаем индексы шифра и переводим их в строку уже знакомой функцией decode_val():
[72, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100]
И вуаля! Наше зашифрованное слово: Hello world

Ну и главный вызов
if __name__ == "__main__":

    word = 'Hello world'
    key = 'key'
    
    print 'Слово: '+ word
    print 'Ключ: '+ key

    key_encoded = encode_val(key)
    value_encoded = encode_val(word)
 
    print 'Value= ',value_encoded
    print 'Key= ', key_encoded

    shifre = full_encode(value_encoded, key_encoded)
    print 'Шифр=', ''.join(decode_val(shifre))

    decoded = full_decode(shifre, key_encoded)
    print 'Decode list=', decoded
    decode_word_list = decode_val(decoded)
    print 'Word=',''.join(decode_word_list)


В статье постарался все описать так чтобы было максимально понятно даже для самого начинающего в Python. Хотя данный алгоритм шифрования больше не является на 100% надежным, однако он хорошо подойдет для тех кто стал на путь изучения более серьезных вещей, например того же RSA.

Ссылки и код:
Описание шифра Виженера на Википедии
Исходный код на Python
Метки:
Поделиться публикацией
Похожие публикации
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 18
  • +2
    Код может быть вы и понятно написали «даже для самого начинающего в Python», но вот сам алгоритм я так и не вспомнил по коду. Вы бы побольше комментировали, поменьше приводили куски кода. Код всегда можно самому написать, если алгоритм понятен.
    • 0
      Как это делал когда-то я: pastebin.com/Tf1dWXtk
      Но я взял в качестве алфавита всю таблицу ASCII…
      • 0
        Я решил что можно будет немножко усложнить задачу по взлому, если взять определенный набор символов (диапазон ASCII). Тут конечно придется учитывать еще что вы хотите зашифровать — если только англ. текст то сойдет, если еще и русские символы — брать больший диапазон. Ну это сугубо в качестве дополнительной плюшки.
      • +9
        Простите, но если мы все же пишем на питоне, то давайте писать на питоне:
        from itertools import cycle
        def form_dict():
            return dict([(i, chr(i)) for i in range(128)])
        
        def comparator(value, key):
            return dict([(idx, [ch[0], ch[1]])
                        for idx, ch in enumerate(zip(value, cycle(key)))])
        
        def encode_val(word):
            d = form_dict()
            return [k for c in word for k,v in d.items() if v == c]
        
        def full_encode(value, key):
            d = comparator(value, key)
            l = len(form_dict())
            return [(v[0] + v[1]) % l for v in d.values()]
        
        def decode_val(list_in):
            l = len(list_in)
            d = form_dict()
            return [d[i] for i in list_in if i in d]
        
        def full_decode(value, key):
            d = comparator(value, key)
            l = len(form_dict())
            return [(v[0] - v[1]) % l for v in d.values()]
        

        … а не изображать basic-style.
        • –5
          А давайте писать все однострочниками на перле.
          • +7
            Вопрос не столько в однострочниках, сколько в неправильном использовании языковых средств.

            Не зачем обращаться к символам строки по индексу, чтобы сравнить два символа, когда можно итерировать строку посимвольно и сравнивать символы. Не зачем итерировать ключи словаря, чтобы проверить, что искомое значение есть в их списке — hash-lookup будет быстрее и правильней и т.д.

            То, что после устранения этих проблем все функции прекрасно описались через list comprehensions — случайность =)
          • 0
            Или так:

            from itertools import cycle
            
            LEN = 127
            
            def full_encode(value, key):
                return ''.join(map(lambda x: chr((ord(x[0]) + ord(x[1])) % LEN), zip(value, cycle(key))))
            
            def full_decode(value, key):
                return ''.join(map(lambda x: chr((ord(x[0]) - ord(x[1]) + LEN) % LEN), zip(value, cycle(key))))
            
            if __name__ == "__main__":
            
                word = 'Hello world'
                key = 'key'
                
                print 'Слово: '+ word
                print 'Ключ: '+ key
            
                shifre = full_encode(word, key)
                print 'Шифр=', shifre
            
                decoded = full_decode(shifre, key)
                print 'Word=', decoded
            
          • +3
            Как-то мало тут всего. О чем статья — о том как (Pi+Ki) mod 26 на питоне написать? Да и «данный алгоритм шифрования больше не является на 100% надежным» — явное преуменьшение.

            Вот если будет вторая часть — как ломать шифр Виженера — тогда да, уже поинтересней будет.
          • 0
            Если копируете куски вместе с формулами из википедии, то добавили бы от себя, что есть Ci, Pi и Ki в формулах.
            Алгоритмический смысл шифрования заключается в индивидуальном сдвиге для каждого символа исходного текста. А величина этого сдвига берется из символа словаря (его позиции, кода), соотвествующего позиции рассматриваемого символа текста. Вот и получается, что результирующий символ это наш исходный плюс смещение, задаваемое позицией символа из словаря. При этом учитываем размер словаря и не выходим за его пределы. И получаем итоговые формулы.

            Да и код получился очень запутанным. Можно было подобное сделать как-то так:
            # -*- coding: utf-8 -*-
            
            d = [chr(i) for i in range(127)]
            dl = len(d)
            
            prepval = lambda val: zip( range(0,len(val)), val )
            
            enc = lambda ch,key: (ch+key) % dl
            dec = lambda ch,key: (ch-key+dl) % dl
            
            def vigenere(value, key, func):
                kl = len(key)
                value = prepval( value )
                e = [ func( ord(c), ord(key[i%kl]) ) for (i,c) in value ]
                return ''.join( [ d[c] for c in e ] )
            
            src = 'Hello world'
            key = 'key'
            
            tmp = vigenere( src, key, enc )
            print tmp
            print vigenere( tmp, key, dec )
            
            • +4
              prepval(value) можно заменить на enumerate(value).
              range(0, x) эквивалентно range(x).
              Плюс вы упростили исходную задачу, предположив, что мы используем ASCII (это следует из того, что номер символа вы получаете с помощью ord, а не из словаря d).

              Мой вариант:
              # -*- coding: utf-8 -*-
              
              from itertools import cycle, count
              from functools import partial
              
              def get_cypher(my_ord, my_chr, al_size):
                  def process(func, value, key):
                      key = cycle(map(my_ord, key))
                      value = map(my_ord, value)
                      result = map(func, zip(value, key))
                      return ''.join(map(my_chr, result))
                  encrypt = lambda x: (x[0] + x[1]) % al_size
                  decrypt = lambda x: (x[0] - x[1] + al_size) % al_size
                  return partial(process, encrypt), partial(process, decrypt)
              
              # Используем ASCII в качестве алфавита
              encrypt, decrypt = get_cypher(ord, chr, 256)
              
              # Либо предоставляем свой словарь d
              d = map(chr, range(128))
              rd = dict(zip(d, count()))
              encrypt, decrypt = get_cypher(rd.get, d.__getitem__, len(d))
              
              • 0
                прекрасный вариант!
            • +1
              Немного странно выглядит формула P = (C — K + 26) mod 26.
              Почему не написать P = C — K mod 26?
              • 0
                Разница может быть меньше нуля.
                • +1
                  Это не важно. Для деления по модулю есть замечательное свойство a ≡ a ± n (mod n)
                  • 0
                    Да, но мы определили лишь соответствие чисел от 0 до 26 некоторым буквам. Любое другое число просто выходит за рамки условия задачи. Хотя в целом вы правы, python поддерживает отрицательные индексы, и сложение можно просто убрать.
                    • 0
                      Это только на беззнаковых типах.
                      • 0
                        Это только на нормальной реализации.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.