Когда я раньше изучал некоторые цифровые валюты, меня очень привлекла концепция, а именнодоказательство с нулевым разглашением, что относится кДоказывающий может убедить проверяющего в правильности утверждения, не предоставляя проверяющему никакой полезной информации.. С точки зрения непрофессионала, у меня есть secret_key, но я не буду предоставлять этот secret_key верификатору, и пусть верификатор поверит, что я знаю этот secret_key. Удивительно, но сегодня мы говорим не о доказательствах с нулевым разглашением, а о самой базовой криптографии. Студенты, интересующиеся доказательствами с нулевым разглашением, могут пойти и посмотретьzkSNARKs in a nutshell.
Хотя классическая криптография сейчас выглядит очень просто, все же стоит узнать о принципах построения паролей и некоторых методах решения проблем. Сегодня мы будем использовать Python для шифрования, расшифровки и взлома двух известных алгоритмов шифрования. Исходный код этой статьи находится вздесьПолучать.
Шифр Цезаря
вводить
Шифр Цезаря — это тип шифра замены, который относится к замене текущей буквы другой буквой. Например, я и другая сторона договариваемся о замене таблицы: l -> h, o -> a, v -> t, а затем я отправляюloveДля другой стороны, другая сторона будет знать в соответствии с таблицей сравнения, что то, что я отправил, на самом делеhate. Шифр Цезаря использует для сдвига и замены обычные 26 английских букв.Обычно значение сдвига устанавливается равным 3, что эквивалентно a -> d, b -> e, c -> f...
Метод шифрования и дешифрования (зашифровать, расшифровать)
Реализация шифрования и дешифрования приведена ниже:
import string
lowercase = string.ascii_lowercase
def substitution(text, key_table):
text = text.lower()
result = ''
for l in text:
i = lowercase.find(l)
if i < 0:
result += l
else:
result += key_table[i]
return result
def caesar_cypher_encrypt(text, shift):
key_table = lowercase[shift:] + lowercase[:shift]
return substitution(text, key_table)
def caesar_cypher_decrypt(text, shift):
return caesar_cypher_encrypt(text, -shift)Для удобства в методе сохранены пробелы и знаки препинания шифротекста.
В обоих сегодняшних примерах будет использоваться следующий классический зашифрованный текст (зашифрованный текст приглашения Германии Мексике напасть на Соединенные Штаты во время Первой мировой войны, полученный изИнцидент с телеграммой Циммермана) показывать:
We intend to begin on the first of February unrestricted submarine warfare. We shall endeavor in spite of this to keep the United States of America neutral. In the event of this not succeeding, we make Mexico a proposal of alliance on the following basis: make war together, make peace together, generous financial support and an understanding on our part that Mexico is to reconquer the lost territory in Texas, New Mexico, and Arizona. The settlement in detail is left to you. You will inform the President of the above most secretly as soon as the outbreak of war with the United States of America is certain and add the suggestion that he should, on his own initiative, invite Japan to immediate adherence and at the same time mediate between Japan and ourselves. Please call the President's attention to the fact that the ruthless employment of our submarines now offers the prospect of compelling England in a few months to make peace.
использоватьcaesar_cypher_encrypt(text, shift)Мы получим:
zh lqwhqg wr ehjlq rq wkh iluvw ri iheuxdub xquhvwulfwhg vxepdulqh zduiduh. zh vkdoo hqghdyru lq vslwh ri wklv wr nhhs wkh xqlwhg vwdwhv ri dphulfd qhxwudo. lq wkh hyhqw ri wklv qrw vxffhhglqj, zh pdnh phalfr d sursrvdo ri dooldqfh rq wkh iroorzlqj edvlv: pdnh zdu wrjhwkhu, pdnh shdfh wrjhwkhu, jhqhurxv ilqdqfldo vxssruw dqg dq xqghuvwdqglqj rq rxu sduw wkdw phalfr lv wr uhfrqtxhu wkh orvw whuulwrub lq whadv, qhz phalfr, dqg dulcrqd. wkh vhwwohphqw lq ghwdlo lv ohiw wr brx. brx zloo lqirup wkh suhvlghqw ri wkh deryh prvw vhfuhwob dv vrrq dv wkh rxweuhdn ri zdu zlwk wkh xqlwhg vwdwhv ri dphulfd lv fhuwdlq dqg dgg wkh vxjjhvwlrq wkdw kh vkrxog, rq klv rzq lqlwldwlyh, lqylwh mdsdq wr lpphgldwh dgkhuhqfh dqg dw wkh vdph wlph phgldwh ehwzhhq mdsdq dqg rxuvhoyhv. sohdvh fdoo wkh suhvlghqwv dwwhqwlrq wr wkh idfw wkdw wkh uxwkohvv hpsorbphqw ri rxu vxepdulqhv qrz riihuv wkh survshfw ri frpshoolqj hqjodqg lq d ihz prqwkv wr pdnh shdfh.
Примечание. Зашифрованный текст, перехваченный британской разведывательной службой, не шифруется с использованием шифра Цезаря таким образом.
трескаться
Что бы вы подумали, если бы перехватили такую телеграмму в то время? После короткого периода замешательства стало очевидно, что он должен найти способ расшифровать нормальное значение. Идея взлома на самом деле очень проста: поскольку значение сдвига может быть установлено искусственно во время шифрования, мы можем циклически переключаться от 0 до 25, чтобы увидеть, какое из них имеет смысл:
def crack_caesar_cypher(text):
for i in range(26):
key_table = lowercase[-i:] + lowercase[:-i]
print(substitution(text, key_table)[:12], '| shift is ', i, )Проверьте результаты:
Какая строка имеет смысл?
шифр Виженера
вводить
Шифр Цезаря, очевидно, не может остановить человеческую мудрость.На самом деле размер пробела нормального шифра замены равен 26!Это очень большое число, которое эквивалентно 88-й степени числа 2. Это случайная замена алфавита на создать таблицу шифрования, а затем шифровать и шифровать в соответствии с таблицей шифрования.Расшифровка, но также не удалось при частотном анализе слов. Затем появился Кодекс Вирджинии. Метод шифрования пароля Вирджинии также очень прост, сначала установитеkey = 'crypto', а затем циклически располагать ключи и исходную информацию во взаимно-однозначном соответствии с исходной информацией, затем складывать позиции букв в алфавите для получения индекса, а затем по модулю 26 для получения зашифрованных букв. алфавита. Например:
we intend to
cr yptocr yp
эквивалентно:
22 4 8 13 19 4 13 3 19 14
2 17 24 15 19 14 2 17 24 15
Складывая вверх и вниз, получаем:
24 21 32 28 38 18 15 20 43 29 по модулю 26, чтобы получить:
24 21 6 2 12 18 15 20 17 3
Тогда в соответствии с алфавитом получаем:
yv gcmspu rd
Метод шифрования и дешифрования (зашифровать, расшифровать)
Реализация шифрования и дешифрования приведена ниже:
def insert_letter(text, i, l):
return text[:i] + l + text[i:]
def get_blank_record(text):
text = text.lower()
blank_record = []
for i in range(len(text)):
l = text[i]
item = []
if lowercase.find(l) < 0:
item.append(i)
item.append(l)
blank_record.append(item)
return blank_record
def restore_blank_record(text, blank_record):
for i in blank_record:
text = insert_letter(text, i[0], i[1])
return text
def get_vigener_key_table(text, key):
text = text.lower()
trim_text = ''
for l in text:
if lowercase.find(l) >= 0:
trim_text += l
total_length = len(trim_text)
key_length = len(key)
quotient = total_length // key_length
reminder = total_length % key_length
key_table = quotient * key + key[:reminder]
return trim_text, key_table
def vigener_cypher_encrypt(text, key, is_encrypt=True):
blank_record = get_blank_record(text)
trim_text, key_table = get_vigener_key_table(text, key)
result = ''
for i in range(len(trim_text)):
l = trim_text[i]
index_lowercase = lowercase.find(l)
index_key_table = lowercase.find(key_table[i])
if not is_encrypt:
index_key_table = -index_key_table
result += lowercase[(index_lowercase + index_key_table) % 26]
return restore_blank_record(result, blank_record)
def vigener_cypher_decrypt(text, key):
return vigener_cypher_encrypt(text, key, False)использоватьvigener_cypher_encrypt(text, key)Мы получим:
yv gcmspu rd usizl dg hjv dxkgv fd uxptlygr ipichmfktrtw gwskpkwpv upktcic. lx gjrja xbfvykhf ke qebhg fd iawu km zxsr kft nbkkcs lhckch ht cdcgbqc ecjmfcc. gc mvg vttgh qw rwbg pfr hnqevcsbbi, nc btyg dcmbqq r nghdqjya ht ccjxtbev mc mvg wmaecyzlv uouzq: btyg nyg mcivrwxf, orit isctc ihugkftk, ugecghiu wgctbezya lirgmgm opu yc nbfvphmopugcz cp fsg iotk rwth ovvxvc kj rd kseflfnst kft ecuk rtkfkkmgr wp kcmtg, pvu bxlktm, pgr cigohbc. kft lsvkjtfspk gc wsvrga bg nvdi mc afs. nhi yzja bbhfpb mvg gptlwfvli ht vyc pucxv kdlh uvagxhnp yh lcqe yh mvg fsiufgri dy kci uxmv vyc jgwvvb hmovvq dy oovpxvo kj atkhczl pgr cub ias ulevxgvzmc mvck ft lvqljs, hb jzq dpb kegibovztt, bbxzrt corrl ih wodcsbovv ysastvlrx opu yi mvg jybx hkdc bxrkrrt usvnctg xcgyc tbf fsglsnmch. izgrqt vonc rwx dtvqxwspkq pmhgerxhb vf rwx tctr iaov kft kivyjtlg gdnahmovli ht qlp hnporpxgsu eml hthvph mvg gpdldgtr dy qqdntezkee tgunrls bb c wcl fcpkfh mc orit isctc.
Для удобства в методе сохранены пробелы и знаки препинания шифротекста.
Приведенный выше шифртекст похож на шифр Цезаря, но в то время этот метод шифрования было трудно взломать.
трескаться
Особенность этого шифрования в том, что одни и те же буквы не будут указывать на один и тот же шифротекст после шифрования, например, первые три словаwe intent toБуква t в шифре соответствует определенной букве шифра Цезаря или обычного шифра замены, но здесь мы можем видетьintentсерединаtзашифрован какm,toсерединаtзашифрован какr. В таком случае,Частотный анализ словтоже не работает.
Но дорога высотой в один фут и дьявол высотой в один фут, и этот пароль, о котором говорят, что его невозможно взломать, предвещал судьбу быть взломанным:
Предположим, я знаю, что длина этого ключа равна 6. Затем мы разрезаем зашифрованный текст на группы по 6, тогда частота исходных букв, соответствующих каждой букве в группе, соответствует частотному анализу слов, Так называемый частотный анализ слов:Частота появления 26 английских букв в предложении.
Затем мы начинаем подсчитывать частоту слов каждой группы:
group 0 : [{'c': 17}, {'g': 16}, {'v': 14}, {'p': 13}, {'k': 11}, {'o': 7}, {'q': 7}]
group 1 : [{'v': 23}, {'k': 17}, {'r': 11}, {'f': 10}, {'z': 10}, {'e': 8}, {'d': 6}]
group 2 : [{'c': 20}, {'r': 15}, {'y': 12}, {'l': 9}, {'g': 8}, {'m': 8}, {'p': 8}]
group 3 : [{'t': 22}, {'h': 11}, {'i': 11}, {'g': 10}, {'c': 9}, {'d': 9}, {'x': 8}]
group 4 : [{'m': 18}, {'h': 15}, {'x': 13}, {'b': 11}, {'l': 10}, {'g': 8}, {'k': 8}]
group 5 : [{'s': 16}, {'b': 14}, {'o': 13}, {'c': 10}, {'h': 10}, {'v': 9}, {'g': 8}]
По алфавитной таблице частот находим, что алфавитeвстречается более чем в 12% случаев, поэтому мы предполагаем, что по крайней мере одна из каждой группы является буквойeСоответствующий зашифрованный текст, затем просмотрите буквы, которые встречаются более 10 раз, и проанализируйте два других массива символов с наибольшей частотой.['t', 'a']Оценка обнаружений и получить наиболее вероятныеkey.
Вот код:
def get_trim_text(text):
text = text.lower()
trim_text = ''
for l in text:
if lowercase.find(l) >= 0:
trim_text += l
return trim_text
def crack_vigener_cypher(text, key_length):
blank_record = get_blank_record(text)
trim_text = get_trim_text(text)
group = ['' for i in range(key_length)]
for i in range(len(trim_text)):
l = trim_text[i]
for j in range(key_length):
if i % key_length == j:
group[j] += l
key = ''
letter_stats_group = []
for j in range(key_length):
letter_stats = []
for l in lowercase:
lt = {}
count = group[j].count(l)
lt[l] = count
letter_stats.append(lt)
letter_stats = sorted(letter_stats, key=lambda x: list(x.values())[0], reverse=True)
letter_stats_group.append(letter_stats)
# print('group', j, ':', letter_stats[:8])
# gvctxs
score_list = []
for i in range(3):
current_letter = list(letter_stats[i].keys())[0]
index = lowercase.find(current_letter)
key_letter = lowercase[index - lowercase.find('e')]
item = []
item.append(key_letter)
score = 0
for k in range(3):
vl = list(letter_stats[k].keys())[0]
for fl in ['t', 'a']:
#if i == 1 and (k == 1 or k == 2) and j == 1:
if (lowercase.find(key_letter) + lowercase.find(fl)) % 26 == lowercase.find(vl):
score += 1
item.append(score)
score_list.append(item)
score_list = sorted(score_list, key=lambda x: x[1], reverse=True)
key += score_list[0][0]
plain_text = vigener_cypher_decrypt(trim_text, key)
return restore_blank_record(plain_text, blank_record)Затем мы бежимcrack_vigener_cypher(cypher_text, 6)Вы можете получить открытый текст. Однако, как вы можете видеть здесь, я по умолчанию передал параметр 6, который является длиной ключа. Но когда мы перехватываем зашифрованный текст, мы даже не знаем ключа и, очевидно, не знаем длины ключа. Итак, если мы сможем определить длину ключа, то шифр Вирджинии перед нами будет бумажным тигром.
На самом деле, как и в шифре Цезаря, можно попробовать от 1 до 25, но здесь мы используем код, называемыйиндекс совпаденияметод, чтобы помочь сузить сферу (хотя фактический эффект не очень хороший, но все же необходимо понять метод).
Метод индекса совпадения: в осмысленном тексте, состоящем из 26 букв, вероятность того, что любые два элемента в точности совпадают, составляет около 0,067, поэтому, если часть открытого текста зашифрована одной и той же буквой, эта вероятность все равно не изменится.
Итак, мы можем написать метод для вычисления индекса совпадения:
def get_coincidence_index(text):
trim_text = get_trim_text(text)
length = len(trim_text)
letter_stats = []
for l in lowercase:
lt = {}
count = trim_text.count(l)
lt[l] = count
letter_stats.append(lt)
index = 0
for d in letter_stats:
v = list(d.values())[0]
index += (v/length) ** 2
return indexЗатем мы предполагаем разные длины ключей, вычисляем индекс совпадения для каждой группы шифротекстов, а затем в качестве альтернативы выбираем часть длины с меньшей дисперсией, чем 0,067:
def get_var(data, mean=0.067):
if not data:
return 0
var_sum = 0
for d in data:
var_sum += (d - mean) ** 2
return var_sum / len(data)
def get_key_length(text):
trim_text = get_trim_text(text)
# assume text length less than 26
group = []
for n in range(1, 26):
group_str = ['' for i in range(n)]
for i in range(len(trim_text)):
l = trim_text[i]
for j in range(n):
if i % n == j:
group_str[j] += l
group.append(group_str)
var_list = []
length = 1
for text in group:
data = []
for t in text:
index = get_coincidence_index(t)
data.append(index)
var_list.append([length, get_var(data)])
length += 1
var_list = sorted(var_list, key=lambda x: x[1])
return [v[0] for v in var_list[:12]][[16, 2.9408699990533694e-05], [9, 3.8755178005797864e-05], [10, 5.415541187702294e-05], [17, 5.5154370298645345e-05], [19, 6.055960902865477e-05], [13, 8.572621594737114e-05], [8, 8.734954157595401e-05], [14, 9.767402405996375e-05], [3, 0.00010208649957333127], [20, 0.00012009258116435503], [11, 0.0001230940714957638], [6, 0.00014687184215509398]]
Правильная длина - 12-й, и я тоже в отчаянии...
Теперь, когда все на месте, перейдите напрямую к альтернативной длине ключа, а затем посмотрите на результат после расшифровки.
12 строк, вы должны увидеть ответ с первого взгляда.
На этом статья заканчивается, критика и исправления приветствуются.