Классический криптоанализ / Хабр
На протяжении многих веков люди придумывали хитроумные способы сокрытия информации — шифры, в то время как другие люди придумывали еще более хитроумные способы вскрытия информации — методы взлома.
В этом топике я хочу кратко пройтись по наиболее известным классическим методам шифрования и описать технику взлома каждого из них.
Шифр Цезаря
Самый легкий и один из самых известных классических шифров — шифр Цезаря отлично подойдет на роль аперитива.
Шифр Цезаря относится к группе так называемых одноалфавитных шифров подстановки. При использовании шифров этой группы «каждый символ открытого текста заменяется на некоторый, фиксированный при данном ключе символ того же алфавита»
wiki.
Способы выбора ключей могут быть различны. В шифре Цезаря ключом служит произвольное число k, выбранное в интервале от 1 до 25. Каждая буква открытого текста заменяется буквой, стоящей на k знаков дальше нее в алфавите. К примеру, пусть ключом будет число 3. Тогда буква A английского алфавита будет заменена буквой D, буква B — буквой E и так далее.
Для наглядности зашифруем слово HABRAHABR шифром Цезаря с ключом k=7. Построим таблицу подстановок:
| 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 |
| h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | a | b | c | d | e | f | g |
И заменив каждую букву в тексте получим: C(‘HABRAHABR’, 7) = ‘OHIYHOHIY’.
При расшифровке каждая буква заменяется буквой, стоящей в алфавите на k знаков раньше: D(‘OHIYHOHIY’, 7) = ‘HABRAHABR’.
Криптоанализ шифра Цезаря
Малое пространство ключей (всего 25 вариантов) делает брут-форс самым эффективным и простым вариантом атаки.
Для вскрытия необходимо каждую букву шифртекста заменить буквой, стоящей на один знак левее в алфавите. Если в результате этого не удалось получить читаемое сообщение, то необходимо повторить действие, но уже сместив буквы на два знака левее. И так далее, пока в результате не получится читаемый текст.
Аффиный шифр
Рассмотрим немного более интересный одноалфавитный шифр подстановки под названием аффиный шифр. Он тоже реализует простую подстановку, но обеспечивает немного большее пространство ключей по сравнению с шифром Цезаря. В аффинном шифре каждой букве алфавита размера
ставится в соответствие число из диапазона 0…
m-1. Затем при помощи специальной формулы, вычисляется новое число, которое заменит старое в шифртексте.
Процесс шифрования можно описать следующей формулой:
,
где x — номер шифруемой буквы в алфавите; m — размер алфавита; a, b — ключ шифрования.
Для расшифровки вычисляется другая функция:
,
где a-1 — число обратное a по модулю m. Это значит, что для корректной расшифровки число a должно быть взаимно простым с m.
С учетом этого ограничения вычислим пространство ключей аффиного шифра на примере английского алфавита. Так как английский алфавит содержит 26 букв, то в качестве a может быть выбрано только взаимно простое с 26 число. Таких чисел всего двенадцать: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 и 25. Число b в свою очередь может принимать любое значение в интервале от 0 до 25, что в итоге дает нам 12*26 = 312 вариантов возможных ключей.
Криптоанализ аффиного шифра
Очевидно, что и в случае аффиного шифра простейшим способом взлома оказывается перебор всех возможных ключей. Но в результате перебора получится 312 различных текстов. Проанализировать такое количество сообщений можно и в ручную, но лучше автоматизировать этот процесс, используя такую характеристику как частота появления букв.
Давно известно, что буквы в естественных языках распределены не равномерно. К примеру, частоты появления букв английского языка в текстах имеют следующие значения:
Т.е. в английском тексте наиболее встречающимися буквами будут E, T, A. В то время как самыми редкими буквами являются J, Q, Z. Следовательно, посчитав частоту появления каждой буквы в тексте мы можем определить насколько частотная характеристика текста соответствует английскому языку.
Для этого необходимо вычислить значение:
,
где n
Чем больше значение χ, тем больше вероятность того, что текст написан на естественном языке.
Таким образом, для взлома аффиного шифра достаточно перебрать 312 возможных ключей и вычислить значение χ для полученного в результате расшифровки текста. Текст, для которого значение χ окажется максимальным, с большой долей вероятности и является зашифрованным сообщением.
Разумеется следует учитывать, что метод не всегда работает с короткими сообщениями, в которых частотные характеристики могут сильно отличатся от характеристик естественного языка.
Шифр простой замены
Очередной шифр, относящийся к группе одноалфавитных шифров подстановки. Ключом шифра служит перемешанный произвольным образом алфавит. Например, ключом может быть следующая последовательность букв: XFQABOLYWJGPMRVIHUSDZKNTEC.
При шифровании каждая буква в тексте заменяется по следующему правилу. Первая буква алфавита замещается первой буквой ключа, вторая буква алфавита — второй буквой ключа и так далее. В нашем примере буква A будет заменена на X, буква B на F.
При расшифровке буква сперва ищется в ключе и затем заменяется буквой стоящей в алфавите на той же позиции.
Криптоанализ шифра простой замены
Пространство ключей шифра простой замены огромно и равно количеству перестановок используемого алфавита. Так для английского языка это число составляет 26! = 288. Разумеется наивный перебор всех возможных ключей дело безнадежное и для взлома потребуется более утонченная техника, такая как поиск восхождением к вершине:
- Выбирается случайная последовательность букв — основной ключ. Шифртекст расшифровывается с помощью основного ключа. Для получившегося текста вычисляется коэффициент, характеризующий вероятность принадлежности к естественному языку.
- Основной ключ подвергается небольшим изменениям (перестановка двух произвольно выбранных букв). Производится расшифровка и вычисляется коэффициент полученного текста.
- Если коэффициент выше сохраненного значения, то основной ключ заменяется на модифицированный вариант.
- Шаги 2-3 повторяются пока коэффициент не станет постоянным.
Для вычисления коэффициента используется еще одна характеристика естественного языка —
частота встречаемости триграмм.Чем ближе текст к английскому языку тем чаще в нем будут встречаться такие триграммы как THE, AND, ING. Суммируя частоты появления в естественном языке всех триграмм, встреченных в тексте получим коэффициент, который с большой долей вероятности определит текст, написанный на естественном языке.
Шифр Полибия
Еще один шифр подстановки. Ключом шифра является квадрат размером 5*5 (для английского языка), содержащий все буквы алфавита, кроме J.
При шифровании каждая буква исходного текста замещается парой символов, представляющих номер строки и номер столбца, в которых расположена замещаемая буква. Буква a будет замещена в шифртексте парой BB, буква b — парой EB и так далее. Так как ключ не содержит букву J, перед шифрованием в исходном тексте J следует заменить на I.
Например, зашифруем слово HABRAHABR. C(‘HABRAHABR’) = ‘AB BB EB DA BB AB BB EB DA’.
Криптоанализ шифра Полибия
Шифр имеет большое пространство ключей (25! = 283 для английского языка). Однако единственное отличие квадрата Полибия от предыдущего шифра заключается в том, что буква исходного текста замещается двумя символами.
Поэтому для атаки можно использовать методику, применяемую при взломе шифра простой замены — поиск восхождением к вершине.
В качестве основного ключа выбирается случайный квадрат размером 5*5. В ходе каждой итерации ключ подвергается незначительным изменениям и проверяется насколько распределение триграмм в тексте, полученном в результате расшифровки, соответствует распределению в естественном языке.
Перестановочный шифр
Помимо шифров подстановки, широкое распространение также получили перестановочные шифры. В качестве примера опишем
Шифр вертикальной перестановки.
В процессе шифрования сообщение записывается в виде таблицы. Количество колонок таблицы определяется размером ключа. Например, зашифруем сообщение WE ARE DISCOVERED. FLEE AT ONCE с помощью ключа 632415.
Так как ключ содержит 6 цифр дополним сообщение до длины кратной 6 произвольно выбранными буквами QKJEU и запишем сообщение в таблицу, содержащую 6 колонок, слева направо:
Для получения шифртекста выпишем каждую колонку из таблицы в порядке, определяемом ключом: EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE.
При расшифровке текст записывается в таблицу по колонкам сверху вниз в порядке, определяемом ключом.
Криптоанализ перестановочного шифра
Лучшим способом атаки шифра вертикальной перестановки будет полный перебор всех возможных ключей малой длины (до 9 включительно — около 400 000 вариантов). В случае, если перебор не дал желаемых результатов, можно воспользоваться поиском восхождением к вершине.
Для каждого возможного значения длины осуществляется поиск наиболее правдоподобного ключа. Для оценки правдоподобности лучше использовать частоту появления триграмм. В результате возвращается ключ, обеспечивающий наиболее близкий к естественному языку текст расшифрованного сообщения.
Шифр Плейфера
Шифр Плейфера — подстановочный шифр, реализующий замену биграмм. Для шифрования необходим ключ, представляющий собой таблицу букв размером 5*5 (без буквы J).
Процесс шифрования сводится к поиску биграммы в таблице и замене ее на пару букв, образующих с исходной биграммой прямоугольник.
Рассмотрим, в качестве примера следующую таблицу, образующую ключ шифра Плейфера:
Зашифруем пару ‘WN’. Буква W расположена в первой строке и первой колонке. А буква N находится во второй строке и третьей колонке. Эти буквы образуют прямоугольник с углами W-E-S-N. Следовательно, при шифровании биграмма WN преобразовывается в биграмму ES.
Криптоанализ шифра Плейфера
Так как ключ шифра Плейфера представляет собой таблицу, содержащую 25 букв английского алфавита, можно ошибочно предположить, что метод поиска восхождением к вершине — лучший способ взлома данного шифра. К сожалению, этот метод не будет работать. Достигнув определенного уровня соответствия текста, алгоритм застрянет в точке локального максимума и не сможет продолжить поиск.
Чтобы успешно взломать шифр Плейфера лучше воспользоваться алгоритмом имитации отжига.
Отличие алгоритма имитации отжига от поиска восхождением к вершине заключается в том, что последний на пути к правильному решению никогда не принимает в качестве возможного решения более слабые варианты. В то время как алгоритм имитации отжига периодически откатывается назад к менее вероятным решениям, что увеличивает шансы на конечный успех.
Суть алгоритма сводится к следующим действиям:
- Выбирается случайная последовательность букв — основной-ключ. Шифртекст расшифровывается с помощью основного ключа. Для получившегося текста вычисляется коэффициент, характеризующий вероятность принадлежности к естественному языку.
- Основной ключ подвергается небольшим изменениям (перестановка двух произвольно выбранных букв, перестановка столбцов или строк). Производится расшифровка и вычисляется коэффициент полученного текста.
- Если коэффициент выше сохраненного значения, то основной ключ заменяется на модифицированный вариант.
- В противном случае замена основного ключа на модифицированный происходит с вероятностью, напрямую зависящей от разницы коэффициентов основного и модифицированного ключей.
- Шаги 2-4 повторяются около 50 000 раз.
Алгоритм периодически замещает основной ключ, ключом с худшими характеристиками. При этом вероятность замены зависит от разницы характеристик, что не позволяет алгоритму принимать плохие варианты слишком часто.
Для расчета коэффициентов, определяющих принадлежность текста к естественному языку лучше всего использовать частоты появления триграмм.
Шифр Виженера
Шифр Виженера относится к группе полиалфавитных шифров подстановки. Это значит, что в зависимости от ключа одна и та же буква открытого текста может быть зашифрована в разные символы. Такая техника шифрования скрывает все частотные характеристики текста и затрудняет криптоанализ.
Шифр Виженера представляет собой последовательность нескольких шифров Цезаря с различными ключами.
Продемонстрируем, в качестве примера, шифрование слова HABRAHABR с помощью ключа 123. Запишем ключ под исходным текстом, повторив его требуемое количество раз:
Цифры ключа определяют на сколько позиций необходимо сдвинуть букву в алфавите для получения шифртекста. Букву H необходимо сместить на одну позицию — в результате получается буква I, букву A на 2 позиции — буква C, и так далее. Осуществив все подстановки, получим в результате шифртекст: ICESCKBDU.
Криптоанализ шифра Виженера
Первая задача, стоящая при криптоанализе шифра Виженера заключается в нахождении длины, использованного при шифровании, ключа.
Для этого можно воспользоваться индексом совпадений.
Индекс совпадений — число, характеризующее вероятность того, что две произвольно выбранные из текста буквы окажутся одинаковы.
Для любого текста индекс совпадений вычисляется по формуле:
,
где fi — количество появлений i-й буквы алфавита в тексте, а n — количество букв в тексте.
Для английского языка индекс совпадений имеет значение 0.0667, в то время как для случайного набора букв этот показатель равен 0.038.
Более того, для текста зашифрованного с помощью одноалфавитной подстановки, индекс совпадений также равен 0.0667. Это объясняется тем, что количество различных букв в тексте остается неизменным.
Это свойство используется для нахождения длины ключа шифра Виженера. Из шифртекста по очереди выбираются каждая вторая буквы и для полученного текста считается индекс совпадений. Если результат примерно соответствует индексу совпадений естественного языка, значит длина ключа равна двум. В противном случае из шифртекста выбирается каждая третья буква и опять считается индекс совпадений. Процесс повторяется пока высокое значение индекса совпадений не укажет на длину ключа.
Успешность метода объясняется тем, что если длина ключа угадана верно, то выбранные буквы образуют шифртекст, зашифрованный простым шифром Цезаря. И индекс совпадений должен быть приблизительно соответствовать индексу совпадений естественного языка.
После того как длина ключа будет найдена взлом сводится к вскрытию нескольких шифров Цезаря. Для этого можно использовать способ, описанный в первом разделе данного топика.
P.S.
Исходники всех вышеописанных шифров и атак на них можно посмотреть на
GitHub.
Ссылки
1. Криптоанализ классических шифров на сайте
practicalcryptography.com.
2. Частотные характеристики английского языка на сайте
practicalcryptography.com3. Описание алгоритма имитации отжига на
wikipedia4. Описание поиска восхождением к вершине на
wikipediaПростой Подстановочный Шифр — CoderLessons.com
Простой шифр замещения является наиболее часто используемым шифром и включает в себя алгоритм замены каждого символа простого текста на каждый символ текста шифра. В этом процессе алфавиты перемешиваются по сравнению с алгоритмом шифрования Цезаря.
пример
Ключи для простого подстановочного шифра обычно состоят из 26 букв. Пример ключа —
plain alphabet : abcdefghijklmnopqrstuvwxyz cipher alphabet: phqgiumeaylnofdxjkrcvstzwb
Пример шифрования с использованием вышеуказанного ключа:
plaintext : defend the east wall of the castle ciphertext: giuifg cei iprc tpnn du cei qprcni
В следующем коде показана программа для реализации простого шифра замещения —
import random, sys
LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
def main():
message = ''
if len(sys.argv) > 1:
with open(sys.argv[1], 'r') as f:
message = f.read()
else:
message = raw_input("Enter your message: ")
mode = raw_input("E for Encrypt, D for Decrypt: ")
key = ''
while checkKey(key) is False:
key = raw_input("Enter 26 ALPHA key (leave blank for random key): ")
if key == '':
key = getRandomKey()
if checkKey(key) is False:
print('There is an error in the key or symbol set.')
translated = translateMessage(message, key, mode)
print('Using key: %s' % (key))
if len(sys.argv) > 1:
fileOut = 'enc.' + sys.argv[1]
with open(fileOut, 'w') as f:
f.write(translated)
print('Success! File written to: %s' % (fileOut))
else: print('Result: ' + translated)
# Store the key into list, sort it, convert back, compare to alphabet.
def checkKey(key):
keyString = ''.join(sorted(list(key)))
return keyString == LETTERS
def translateMessage(message, key, mode):
translated = ''
charsA = LETTERS
charsB = key
# If decrypt mode is detected, swap A and B
if mode == 'D':
charsA, charsB = charsB, charsA
for symbol in message:
if symbol.upper() in charsA:
symIndex = charsA.find(symbol.upper())
if symbol.isupper():
translated += charsB[symIndex].upper()
else:
translated += charsB[symIndex].lower()
else:
translated += symbol
return translated
def getRandomKey():
randomList = list(LETTERS)
random.shuffle(randomList)
return ''.join(randomList)
if __name__ == '__main__':
main()Выход
При реализации приведенного выше кода вы можете наблюдать следующий вывод:
10 популярных кодов и шифров
Коды и шифры — не одно и то же: в коде каждое слово заменяется другим, в то время как в шифре заменяются все символы сообщения.
В данной статье мы рассмотрим наиболее популярные способы шифрования, а следующим шагом будет изучение основ криптографии.
- Стандартные шифры
- Цифровые шифры
- Как расшифровать код или шифр?
Стандартные шифры
ROT1
Этот шифр известен многим детям. Ключ прост: каждая буква заменяется на следующую за ней в алфавите. Так, А заменяется на Б, Б — на В, и т. д. Фраза «Уйрйшоьк Рспдсбннйту» — это «Типичный Программист».
Попробуйте расшифровать сообщение:
Лбл еёмб, рспдсбннйту?Сумели? Напишите в комментариях, что у вас получилось.
Шифр транспонирования
В транспозиционном шифре буквы переставляются по заранее определённому правилу. Например, если каждое слово пишется задом наперед, то из hello world получается dlrow olleh. Другой пример — менять местами каждые две буквы. Таким образом, предыдущее сообщение станет eh ll wo ro dl.
Ещё можно использовать столбчатый шифр транспонирования, в котором каждый символ написан горизонтально с заданной шириной алфавита, а шифр создаётся из символов по вертикали. Пример:
Из этого способа мы получим шифр holewdlo lr. А вот столбчатая транспозиция, реализованная программно:
def split_len(seq, length):
return [seq[i:i + length] for i in range(0, len(seq), length)]
def encode(key, plaintext):
order = {
int(val): num for num, val in enumerate(key)
}
ciphertext = ''
for index in sorted(order.keys()):
for part in split_len(plaintext, len(key)):
try:ciphertext += part[order[index]]
except IndexError:
continue
return ciphertext
print(encode('3214', 'HELLO'))Азбука Морзе
В азбуке Морзе каждая буква алфавита, цифры и наиболее важные знаки препинания имеют свой код, состоящий из череды коротких и длинных сигналов:
Чаще всего это шифрование передаётся световыми или звуковыми сигналами.
Сможете расшифровать сообщение, используя картинку?
•−− −•− −−− −• −•−• • ••• − •− − −••− •• • ••• − −••− −•• • −−−− •• ••−• •−• •− − −−− •−• −•−− Шифр Цезаря
Это не один шифр, а целых 26, использующих один принцип. Так, ROT1 — лишь один из вариантов шифра Цезаря. Получателю нужно просто сообщить, какой шаг использовался при шифровании: если ROT2, тогда А заменяется на В, Б на Г и т. д.
А здесь использован шифр Цезаря с шагом 5:
Иербэй йюк ёурбэй нтчйхйцтаъ энщхужМоноалфавитная замена
Коды и шифры также делятся на подгруппы. Например, ROT1, азбука Морзе, шифр Цезаря относятся к моноалфавитной замене: каждая буква заменяется на одну и только одну букву или символ. Такие шифры очень легко расшифровываются с помощью частотного анализа.
Например, наиболее часто встречающаяся буква в английском алфавите — «E». Таким образом, в тексте, зашифрованном моноалфавитным шрифтом, наиболее часто встречающейся буквой будет буква, соответствующая «E». Вторая наиболее часто встречающаяся буква — это «T», а третья — «А».
Однако этот принцип работает только для длинных сообщений. Короткие просто не содержат в себе достаточно слов.
Шифр Виженера
Представим, что есть таблица по типу той, что на картинке, и ключевое слово «CHAIR». Шифр Виженера использует принцип шифра Цезаря, только каждая буква меняется в соответствии с кодовым словом.
В нашем случае первая буква послания будет зашифрована согласно шифровальному алфавиту для первой буквы кодового слова «С», вторая буква — для «H», etc. Если послание длиннее кодового слова, то для (k*n+1)-ой буквы, где n — длина кодового слова, вновь будет использован алфавит для первой буквы кодового слова.
Чтобы расшифровать шифр Виженера, для начала угадывают длину кодового слова и применяют частотный анализ к каждой n-ной букве послания.
Попробуйте расшифровать эту фразу самостоятельно:
зюм иэлруй южжуглёнъПодсказка длина кодового слова — 4.
Шифр Энигмы
Энигма — это машина, которая использовалась нацистами во времена Второй Мировой для шифрования сообщений.
Есть несколько колёс и клавиатура. На экране оператору показывалась буква, которой шифровалась соответствующая буква на клавиатуре. То, какой будет зашифрованная буква, зависело от начальной конфигурации колес.
Существовало более ста триллионов возможных комбинаций колёс, и со временем набора текста колеса сдвигались сами, так что шифр менялся на протяжении всего сообщения.
Цифровые шифры
В отличие от шифровки текста алфавитом и символами, здесь используются цифры. Рассказываем о способах и о том, как расшифровать цифровой код.
Двоичный код
Текстовые данные вполне можно хранить и передавать в двоичном коде. В этом случае по таблице символов (чаще всего ASCII) каждое простое число из предыдущего шага сопоставляется с буквой: 01100001 = 97 = «a», 01100010 = 98 = «b», etc. При этом важно соблюдение регистра.
Расшифруйте следующее сообщение, в котором использована кириллица:
110100001001101011010000101111101101000010110100Шифр A1Z26
Это простая подстановка, где каждая буква заменена её порядковым номером в алфавите. Только нижний регистр.
Попробуйте определить, что здесь написано:
15-6-2-16-13-30-26-16-11 17-18-10-14-6-18Шифрование публичным ключом
Алгоритм шифрования, применяющийся сегодня буквально во всех компьютерных системах. Есть два ключа: открытый и секретный. Открытый ключ — это большое число, имеющее только два делителя, помимо единицы и самого себя. Эти два делителя являются секретным ключом, и при перемножении дают публичный ключ. Например, публичный ключ — это 1961, а секретный — 37 и 53.
Открытый ключ используется, чтобы зашифровать сообщение, а секретный — чтобы расшифровать.
Как-то RSA выделила 1000 $ в качестве приза тому, кто найдет два пятидесятизначных делителя числа:
1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139Как расшифровать код или шифр?
Для этого применяются специальные сервисы. Выбор такого инструмента зависит от того, что за код предстоит расшифровать. Примеры шифраторов и дешифраторов:
Адаптированный перевод «10 codes and ciphers»
Криптоанализ шифра простой замены Текст научной статьи по специальности «Математика»
CRYPTOANALYSIS OF CIPHER OF SIMPLE REPLACEMENT Sinochkin D.V. (Russian Federation) Email: [email protected]
Sinochkin Denis Vadimovich — Student, DEPARTMENT OF INFORMATICS AND COMPUTER SCIENCE, DON STATE TECHNICAL UNIVERSITY, ROSTOV-ON-DON
Abstract: this article is devoted to the method of hacking the cipher of Caesar with the keyword. Describes the main goals and the need for encryption of information, as well as a method of hacking absolutely any code. An example is given of one of the possible variants of hacking the cipher of a simple substitution with the help of a proximity measure, a proximity matrix of an open text, and frequency characteristics of the plaintext. An example of cryptanalysis of cipher text is given regardless of the length of the key. The dependence of the decryption efficiency on the key length is determined. Keywords: cryptanalysis, encryption, simple replacement code, frequency characteristics.
КРИПТОАНАЛИЗ ШИФРА ПРОСТОЙ ЗАМЕНЫ Синочкин Д.В. (Российская Федерация)
Синочкин Денис Вадимович — студент, факультет информатики и вычислительной техники, Донской государственный технический университет, г. Ростов-на-Дону
Аннотация: данная статья посвящена методу взлома шифра Цезаря с ключевым словом. Описаны основные цели и необходимость шифрования информации, а также рассмотрен метод взлома абсолютно любого шифра. Приведен в пример один из возможных вариантов взлома шифра простой замены с помощью меры близости, матрицы близости открытого текста, а также частотные характеристики открытого текста. Приведен пример криптоанализа шифротекста вне зависимости от длины ключа. Определена зависимость эффективности дешифровки от длины ключа.
Ключевые слова: криптоанализ, шифрование, шифр простой замены, частотные характеристики.
Введение. В настоящий момент существует огромное количество методов шифрования. Главным образом эти методы делятся на симметричные и асимметричные методы, но секретность данных основана не на тайном алгоритме, а на том, что ключ шифрования известен только доверенным лицам. Ключ -важнейший компонент шифра, отвечающий за выбор преобразования, применяемого для шифрования конкретного сообщения [1]. В современном мире криптография находит множество различных применений: для передачи информации, она используется в сотовой связи, платном цифровом телевидении, при подключении к Wi-Fi и на транспорте для защиты билетов от подделок, и в банковских операциях, для электронного документооборота.
Обязательным этапом создания шифра считается изучение его уязвимости к различным известным атакам — криптоанализу [2].
Анализ необходимости шифрования данных. Современные криптографические системы позволяют расшифровать информацию по различным типам алгоритмов буквально в доли секунды. Уровень развития информационных технологий позволяет добиться высокого уровня шифрования, но и при этом дешифрование так же не остается на месте. Несмотря на защищенность каналов связи, информация может быть перехвачена
непосредственно на принимающем устройстве. После этого, если она не была зашифрована должным образом, будет расшифрована злоумышленниками и будет нанесен вред необходимому для него объекту [3].
Современные алгоритмы шифрования разрабатываются таким образом, чтобы аналитик имел как можно меньше шансов отыскать секретный ключ, с помощью которого были зашифрованы данные. Любая система шифрования, кроме абсолютно криптостойких, может быть взломана простым перебором всех возможных ключей. Но перебирать придётся до тех пор, пока не отыщется тот единственный ключ, который и поможет расшифровать шифротекст, то есть необходимо перебрать п! ключей, однако ей сложно выделить правильный текст. Невозможность взлома полным перебором абсолютно криптостойкого шифра так же основана на необходимости выделить в расшифрованном сообщении именно то, которое было зашифровано в криптограмме. Перебирая все возможные ключи и применяя их к абсолютно стойкой системе, криптоаналитик получит множество всех возможных сообщений, которые можно было зашифровать (в нем могут содержаться и осмысленные сообщения).
Основные соображения взлома шифра просто замены. Любой метод вскрытия шифра простой однобуквенной замены основан на том обстоятельстве, что с точностью до переобозначений частотные характеристики т-грамм шифротекста и открытого текста одинаковы. При этом существенно используются априорные частотные характеристики предполагаемого открытого текста. Такие характеристики являются более рельефными для литературных текстов. Чем менее рельефно распределение знаков текста, тем сложнее задача вскрытия шифра простой замены. Далее будем решать задачу вскрытия простой замены лишь для литературных текстов и на статистику. Алгоритм вскрытия простой замены по тексту криптограммы достаточно тяжело формализовать. При любой попытке формализации теряется какой-нибудь важный нюанс. Поэтому укажем лишь основные идеи, лежащие в основе такого алгоритма: подсчет частот встречаемости шифрообозначений, а также некоторых их сочетаний, например, биграмм и триграмм подряд идущих знаков; выявление шифрообозначений, заменяющих гласные и согласные буквы; выдвижение гипотез о значениях шифрообозначений и их проверка. Восстановление истинного значения шифрообозначений.
Если длина текста достаточно велика, то найденные на 1 этапе частоты окажутся близкими к табулированным значениям частот знаков. Хорошим критерием является читаемость восстанавливаемого открытого текста. При проверке гипотез о значениях шифрообозначений полезен поиск в шифротексте слов с характерной структурой, которые часто встречаются в открытом тексте. Если с помощью приведенных соображений произведено несколько идентификаций шифрообозначнеий, то дальнейшая работа по вскрытию текста криптограммы не представляет особого труда. Однако, если известно, что использовался аффинный шифр, то существует критерий, основанный на близости матрицы биграмм
Д(1) = (Дч(1))п.п
данного текста t эталонной матрице биграмм открытого текста
В (Ьц)п*п>
где п — число букв алфавита.
Мерой близости служит следующая целевая функция ОД, связывающая матрицы Л© и В:
и
Будем исходить из того предположения, что если у — данная криптограмма и Dk -правило расшифрования на ключе к данного шифра простой замены, то для истинного ключа к,, значение
31 ■ Еигореап Баепсе № 10(32)
f(Dku(y))= ^Ь(Оки(у))-Ц|
ij
должно быть минимальным.
Идея основного шага алгоритма состоит в гом, чтобы исходя из некоторого первичного «приближения» k для ключа ku, основанного, например, на диаграмме частот букв, немного его изменять неким способом, уменьшая значение целевой функции f(t).
Криптоанализ шифротекста. Для наиболее точного подбор ключа шифротекста необходимо проанализировать частотные характеристики данного текста и сравнить их со статистическими характеристиками русских букв в текстах. Для этого необходимо отсортировать по убыванию частоты букв статистики и шифротекста и сопоставить их в качестве начального ключа. Данный метод позволит точно расшифровать 2-4 символа исходного текста, что не достаточно для полной расшифровки. Поэтому необходим дополнительный алгоритм, состоящий в получении биграмм шифротекста и сопоставления их с биграммами открытого литературного текста, после чего производится подсчет меры совпадения биграмм шифротекста с биграммами открытого текста путем перестановки символом в ключе между собой. Для поиска ключа используется перестановка в нем соседних символов, через символ, через 2 символа, через 5 символов. После осуществления одной из перестановок выбирается наименьшая мера, после которой происходит поиск остальными методами до получения наименьшей меры. Алгоритм перестает работать до тех пор, пока не переберём все методы перестановок. В результате дешифруем полученным ключом текст. Данный алгоритм работает долго из-за сопоставления всех биграмм. В результате получаем наиболее «читаемый» текст с незначительными ошибками. От длины ключа зависит эффективность дешифровки: чем длинее ключ, тем сложнее дешифровать.
Список литературы /References
1. Алферов А.П. Основы криптографии: учебное пособие. М.: Гелиос АРВ, 2002. 480 с.
2. Баричев С.Г. Основы современной криптографии. // Учебный курс. 2-е изд., испр. и доп. М.: Горячая линия — Телеком, 2002. 175 с.
3. Рябко Б.Я. Криптографические методы защиты информации. // Учебное пособие для вузов. 2-е изд. М.: Горячая линия — Телеком, 2012. 22 с.
Список литературы на английском языке /References in English
1. AlferovA.P. Fundamentals of cryptography. // Atutorial. M.: Helios ARV, 2002. 480 p.
2. Barichev S.G. Fundamentals of modern cryptography. // A training course, 2 ed. M.: Gorjachaja linija — Telecom, 2002. 175 p.
3. Rjabko B.Ja. Cryptographic methods of information protection. // Textbook manual for universities, 2 ed. М.: Gorjachaja linija — Telecom, 2012. 229 p.
GFI — программы для защиты сети
Шифр простой замены
Шифры замены — класс методов шифрования, существующий практически столько же, сколько и алфавит. Его суть состоит в замене букв другими буквами, числами или символами (отсылка к криптографии).
Не углубляясь в особенности и тонкости шифра, можно выбрать самый простой метод шифрования — тот, где заменяется каждая буква следующей за ней в алфавите. Для примера возьмем слова «cat» и «dog». Зашифровываем: за с в алфавите идет d (c=d), за a будет b (a=b), ну и за t следует u (t=u). Ta же формула и для второго слова: d=e, o=p, g=h. В результате получаем два шифра — dbu и eph.
Шифр простой замены букв (через две)
Шифр простой замены нельзя назвать очень уж надежным. Его совсем не сложно взломать, если сопоставить несколько зашифрованных предложений или знать принципы использования. Но можно поэкспериментировать и разнообразить метод. Например, задать собственный порядок замены букв, добавить числа и т.д.
Мнемонический код
Можно воспользоваться излюбленным методом фокусников и магов — мнемоникой. Она помогает визуализировать объект с помощью его полного описания, упрощая тем самым запоминание или идентификацию. Подобный принцип используется в известной поговорке про цвета радуги: «Каждый (Красный) охотник (Оранжевый) желает (Желтый) знать (Зеленый), где (Голубой) сидит (Синий) фазан (Фиолетовый)».
В упрощенном виде все выглядит примерно так: «а — это ананас, б — это банан, в — это вишня». Для построения пароля, используйте слова, соответствующие буквам.
Запоминание последовательности цветов радуги
Например, нужно создать пароль для сайта bank.com. Возьмем за основу код из первых двух букв от названия веб-ресурса «b» и «a». Согласно конструкции «b is for banana, a is for apple» получится «bananaapple». Добавьте между ними дефис и пароль приобретет еще и необходимый символ. А если объединить это все с шифром простой замены, пароль для bank.com станет по-истине надежным nsmsms=s[[;r.
Название сайта в конце пароля
Технический директор компании по сетевой безопасности Panda
Security Луис Корронс предлагает следующий вариант:
Чтобы сделать пароль уникальным для каждого сайта (без
необходимости его записывать) можно добавить название веб-ресурса
в его конец.
Рассмотрим подробнее на примере все того же сайта bank.com. К выбранному паролю в конце добавим приставку «-bank». Получится более сложная конструкция, делающая пароль и понятным и сложным. Тоже самое проделываем с учетными записями в социальных сетях «-twitter», «-facebook» и «-linkedin» или сокращенные варианты вроде «-twit», «-face» и «-link».
Временные рамки
Есть компании, которые вынуждают своих клиентов менять пароли раз в полгода или год. Тут тоже можно найти решение. Просто добавляйте необходимый год, квартал к началу или концу пароля. Возьмем за основу уже знакомый пароль «banana», добавим к нему наступающий 2016 год и 1-й квартал. Получается banana-16-q1. А если произвести перемещения всего по одному ключу на клавиатуре, пароль существенно усложнится и обретет вид nsmsms=3-25=j3
И вот — наш уникальный пароль, довольно сложный, надежный, который можно запомнить и без особого труда регулярно изменять (по месяцам или годам).
Размер имеет значение
Помимо шифровки стоит поговорить и о качестве самого пароля. Его длина имеет важное значение. Полный набор включает 26 строчных букв, 26 прописных и 10 цифр. Также в пароле может использоваться приблизительно 30 специальных знаков. Это все говорит о том, что для каждого символа, добавленного к паролю, число возможных вариантов увеличивается в 90 раз.
По словам генерального директора фирмы сетевой безопасности
FlowTraq Винсента Берка:
Большинство веб-сайтов и компаний нуждаются в паролях,
которые насчитывают комбинацию как минимум из 10 символов
нижнего и верхнего регистра, при этом включают число
и один или несколько специальных знаков
В последнее время специалисты по безопасности рекомендуют увеличивать длину пароля вообще до двенадцати знаков. По их мнению 12 — минимум. Данная теория сформировалась на основе исследования, которое было проведено в Технологическом институте (штат Джорджия, США). Исследователи использовали группы видеокарт, чтобы взломать восьмизначные пароли и пришли к выводу, что для этого достаточно двух-трех часов. Для взлома были задействованы графические процессоры — системные компоненты, разработанные для удовлетворения потребностей современных геймеров.
Пароли из семи символов квалифицируются, как «безнадежно несоответствующие». Исследователи, занимающиеся вопросами безопасности данных, пришли к заключению, что на взлом паролей из двенадцати символов с современными технологиями уйдет около 17,000 лет. Правда, технологическое развитие настолько стремительно, что сложно давать точные прогнозы.
Оригинальность пароля
Разумеется, не одна только длина делает пароль надежным. Он не должен быть легким для угадывания или предсказуемым. Например, пароль LadyGaga — хорош только для преданного поклонника или для самой певицы. Набор цифр 1234567890 тоже не пойдет — слишком очевидно, что даже ребенок может его взломать, набирая подряд все десять цифр на клавиатуре. Ненадежной будет и комбинация из серии password1234, пусть даже она состоит из двенадцати символов.
Стоит придумывать сложные и не распространенные пароли. Лучше избегать слов, которые можно найти в словарях любого языка. Популярные замены букв числами (0 вместо «o», 4 вместо «a») не играют особой роли. Не желательно повторять один и тот же пароль много раз. Хотя именно это и делают пользователи, согласно ноябрьскому исследованию RSA 69%. Результаты продемонстрировали, что потребители многократно используют однажды придуманный ими пароль (при том, что почти 50% из них были жертвами атак со стороны хакеров).
Предложения-подсказки
Большинство экспертов по безопасности сходятся во мнении, что пароли должны быть легко запоминающимися, но трудно угадываемыми. Слишком сложные и непонятные комбинации из символов попросту забудутся. А записывать пароли на стикерах, бумажках, в блокнотах или где-то еще — не самая удачная идея. Тут уж лучше ограничится подсказкой, понятной только хозяину, но не кому-то другому.
Один из параметров, делающий пароль более сложным, состоит в том, чтобы использовать действительно жесткие конструкции. Вряд ли кто-то сможет запомнить набор из двадцати знаков, вроде GdzIQaZyVaFgbh7dlu46. Фактически, такие пароли довольно «болезненно» использовать вообще. С другой стороны, их в самом деле будет трудно взломать. Подобные пароли хороши для систем, требующих особой безопасности и не используемых часто.
В качестве пароля можно использовать фразу, предварительно кодируя ее. Например на английском «I want to be at the beach» в кодировке может выглядеть, как iw2b@theBeach. Запоминающийся пароль, который будет достаточно сложным для взлома. Под каждую систему возможно подобрать различное окончание. Некоторые системы позволяют даже использовать полные предложение в качестве паролей. Такие пароли не забудутся и будут довольно надежными.
В целях повышения безопасности данных известным облачным хранилищем данных Dropbox был создан список из паролей, которые запрещено использовать. В списке находится около 85100 паролей.
А Университет Южного Уэльса провел исследования, результаты которого показали, что:
4,7% пользователей используют пароль password;
8,5% пользователей выбирают один из двух вариантов: password или 123456;
9,8% пользователей выбирают один из трёх вариантов: password, 123456 или 12345678;
14% пользователей выбирают один из 10 самых популярных паролей;
40% пользователей выбирают один из 100 самых популярных паролей;
79% пользователей выбирают один из 500 самых популярных паролей;
91% пользователей выбирает один из 1 000 самых популярных паролей.
Источник: habrahabrИллюстрированный самоучитель по защите информации › Основы криптографии › Шифры замены и перестановки [страница — 59] | Самоучители по безопасности
Шифры замены и перестановки
Шифры появились на свет задолго до изобретения компьютера. Получившие широкое распространение криптографические алгоритмы выполняли либо замену одних букв на другие, либо переставляли буквы друг с другом. Самые стойкие шифры делали одновременно и то, и другое, причем многократно.
Шифры замены
Шифром замены называется алгоритм шифрования, который производит замену каждой буквы открытого текста на какой-то символ шифрованного текста. Получатель сообщения расшифровывает его путем обратной замены.
В классической криптографии различают 4 разновидности шифров замены:
- Простая замена, или одноалфавитный шифр. Каждая буква открытого текста заменяется на один и тот же символ шифртекста.
- Омофонная замена. Аналогична простой замене с единственным отличием: каждой букве открытого текста ставятся в соответствие несколько символов шифртекста. Например, буква «А» заменяется на цифру 5, 13, 25 или 57, а буква «Б» – на 7, 19, 31 или 43 и так далее.
- Блочная замена. Шифрование открытого текста производится блоками. Например, блоку «АБА» может соответствовать «РТК», а блоку «АББ» – «СЛЛ».
- Многоалфавитная замена. Состоит из нескольких шифров простой замены. Например, могут использоваться пять шифров простой замены, а какой из них конкретно применяется для шифрования данной буквы открытого текста, – зависит от ее положения в тексте.
Примером шифра простой замены может служить программа ROT13, которую обычно можно найти в операционной системе UNIX. С ее помощью буква «А» открытого текста на английском языке заменяется на букву «N», «В» – на «О» и так далее. Таким образом, ROT13 циклически сдвигает каждую букву английского алфавита на 13 позиций вправо. Чтобы получить исходный открытый текст надо применить функцию шифрования ROT13 дважды:
Р = ROT13(ROT13(P))
Все упомянутые шифры замены легко взламываются с использованием современных компьютеров, поскольку замена недостаточно хорошо маскирует стандартные частоты встречаемости букв в открытом тексте.
Разновидностью шифра замены можно считать код, который вместо букв осуществляет замену слов, фраз и даже целых предложений. Например, кодовый текст «ЛЕДЕНЕЦ» может соответствовать фразе открытого текста «ПОВЕРНУТЬ ВПРАВО НА 90°». Однако коды применимы только при определенных условиях: если, например, в коде отсутствует соответствующее значение для слова «МУРАВЬЕД», то вы не можете использовать это слово в открытом тексте своего сообщения, предназначенном для кодирования.
Шифры перестановки
В шифре перестановки буквы открытого текста не замещаются на другие, а меняется сам порядок их следования. Например, в шифре простой колонной перестановки исходный открытый текст записывается построчно (число букв в строке фиксировано), а шифртекст получается считыванием букв по колонкам. Расшифрование производится аналогично: шифртекст записывается поколонно, а открытый текст можно затем прочесть по горизонтали.
Для повышения стойкости полученный шифртекст можно подать на вход второго шифра перестановки. Существуют еще более сложные шифры перестановки, однако почти все они легко взламываются с помощью компьютера.
Хотя во многих современных криптографических алгоритмах и используется перестановка, ее применение ограничено узкими рамками, поскольку в этом случае требуется память большого объема, а также накладываются ограничения на длину шифруемых сообщений. Замена получила значительно большее распространение.
Вопрос 5.Поточные шифры простой замены
Наибольшее распространение получили поточные шифры простой замены, множества шифрвеличин и шифробозначений которых совпадают с алфавитом открытого текста A. Ключом такого шифра является подстановка k на множестве А, верхняя строка которой представляет собой естественную последовательность букв алфавита, а нижняя — систематически перемешанную или случайную последовательность букв из А
Помимо явного задания (в виде двустрочной записи) ключ может быть задан некоторой формулой, как, например, для определяемого ниже шифра Цезаря(который иногда называют также сдвиговым шифром) и аффинного шифра. При использовании этих шифров буквы алфавита А удобно отождествлять с их порядковыми номерами, так что, например, для латинского алфавита
При использовании этих шифров полезно заменить буквы – их числовыми эквивалентами. Приведем буквы русского алфавита в соответствии с их порядковыми номерами (Таблица 1.1):
Таблица 1.1
| Буква | А | Б | В | Г | Д | Е | Ё |
| Номер | |||||||
| Буква | Ж | З | И | Й | К | Л | М |
| Номер | |||||||
| Буква | Н | О | П | Р | С | Т | У |
| Номер | |||||||
| Буква | Ф | Х | Ц | Ч | Ш | Щ | Ъ |
| Номер | |||||||
| Буква | Ы | Ь | Э | Ю | Я | ||
| Номер |
1. Шифр Цезаря для русского алфавита
Согласно правилу :
.
Для x = (x1,…,xi), y = (y1,…,yi), полагаем , x = Dk(y) = (y1 + (33 – k),…, yi + (33 – k)),
где + и —— операции кольца вычетов Z33.
В качестве примера возьмем исходный текст: «Шифр Цезаря».
Шифрование
Выберем
y1 = Ш = 26 + 5 = 31 = Э,
y2 = Н = 10 + 5 = 15 = Н и т.д.
y10 = Я = 33 + 5 = 38 -5 = 5
Получим криптограмму:
— в цифровом эквиваленте – 31,15,27,23,29,11,14,06,23,05
— в буквенном эквиваленте — ЭНЩХЫЙМЕХД
Дешифрование
Согласноx = Dk(y) = (y1 + (33 – k),…, yi + (33 – k)),расшифруем побуквенно криптограмму :
x1 = Э = 31 = 31 + (33 – 5) = 31 + 28 = 59 -33 = 26 = И
x2 = Н = 15 = 15 + 28 = 43 – 33 = 10 = И …
x5 = Ы = 29 = 29 + 28 = 57 -33 = 24 = Ц …
x10 = Д = 5 = 5 + 28 = 33 = Я
Расшифрованный текст «Шифр Цезаря».
2. Аффинный шифр для русского алфавита
В аффинном шифре каждой букве алфавита размера m ставится в соответствие число из диапазона 0..m − 1. Затем при помощи модульной арифметики для каждого числа, соответствующего букве исходного алфавита, вычисляется новое число, которое заменит старое в шифротексте. Функция шифрования для каждой буквы
где модульm — размер алфавита, а пара a и b — ключ шифра. Значение a должно быть выбрано таким, что a и m — взаимно простые числа.
Функция расшифрования
где — обратное к a число по модулю m. То есть оно удовлетворяет уравнению
Обратное к a число существует только в том случае, когда a и m — взаимно простые. Значит, при отсутствии ограничений на выбор числа a расшифрование может оказаться невозможным. Покажем, что функция расшифрования является обратной к функции шифрования
Количество возможных ключей для аффинного шифра можно записать через функцию Эйлера как .
Таблица 1.2 Для русского алфавита
| Буква | А | Б | В | Г | Д | Е | Ё |
| Цифра | |||||||
| Буква | Ж | З | И | Й | К | Л | М |
| Цифра | |||||||
| Буква | Н | О | П | Р | С | Т | У |
| Цифра | |||||||
| Буква | Ф | Х | Ц | Ч | Ш | Щ | Ъ |
| Цифра | |||||||
| Буква | Ы | Ь | Э | Ю | Я | ||
| Цифра |
В качестве примера возьмем исходный текст: «Аффинный шифр «
Шифрование
Выберем К = (2,4) Данный ключ индуцирует следующую подстановку на Z в соответствии с таблицей 6.2. Согласно
вычислим
Если декодировать числа в буквы, то получим следующее соответствие для букв:
| Д | Ё | З | Й | Л | Н | П |
| С | У | Х | Ч | Щ | Ы | Э |
| Я | Б | Г | Е | Ж | И | К |
| М | О | Р | Т | Ф | Ц | Ш |
| Ъ | Ь | Ю | А | В |
Исходному тексту: «Аффинный шифр «соответствует числовая последовательность x=(0,21,21, 9,14, 14,28,10,25,9,21,17).
При первом способе шифрования буквы исходного текста заменяются на буквы нижнего ряда трансформированной таблицы Y
= ЙВВЦЫЫИЧПЦВЮ.
При втором методе шифрования Yвычисляется по формуле
Y =(0*2+4, 21*2+4, 21*2+4, 9*2+4,14*2+4, 14*2+4, 28*2+4, 10*2+4, 25*2+4, 9*2+4, 21*2+4, 17*2+4)= ( 4,13,13,22,32,32,27,24,21,22,13,5)
Для расшифрованияу следует вычислить 2-1 в группе . Очевидно, что 2-1= 17. Теперь расшифруем у в соответствии с определением правила расшифрования:
x= Dk(х)=((4+29)*17,(13+29)*17,(13+29)*17,(22+29)*17),(32+29)*17,(32+29)*17,(27+29)*17,(24+29)*17,(21+29)*17,(22+29)*17,(13+29)*17,(5+29)*17) = (0,21,21,9,14,14,28,10,25,9,21,17).
Подстановка букв из таблицы 6.2 даёт буквенный исходный текст: «Аффинный шифр».
простых подстановочных шифров | Крипто-IT
Простые подстановочные шифры
Простые шифры подстановки заменяют каждую букву открытого текста другим символом. Трансформация однозначна и обратима.
Использование
Ранние простые подстановочные шифры использовались еще в древности. Они были одним из первых (после стеганографии) способов защиты сообщений.
Описание
Простые шифры подстановки работают, заменяя каждый символ открытого текста другим символом.Для декодирования букв зашифрованного текста следует использовать обратную подстановку и поменять буквы обратно.
Перед использованием подстановочного шифра следует выбрать подстановки, которые будут использоваться для замены всех букв алфавита. Это можно сделать, написав все буквы алфавита в алфавитном порядке в первой строке, а затем во второй строке те же буквы, но в любом другом случайном порядке. Буквы из верхнего и нижнего рядов образуют пары, которые следует использовать при шифровании.
Например, давайте рассмотрим следующие две последовательности букв, которые определяют шифр замещения:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
TIMEODANSFRBCGHJKLPQUVWXYZ
Можно заметить, что буква F кодируется с помощью буквы D, в то время как та же буква F в зашифрованном тексте соответствует мусору открытого текста J. С другой стороны, буква Z соответствует букве Z (она не изменяется при шифровании).
Смешение алфавита можно продолжить, определив ключевое слово (или несколько ключевых слов), записав его (пропуская повторяющиеся буквы) под исходными буквами алфавита и заполнив оставшиеся пустые места в конце оставшимися буквами алфавита.Это упрощает запоминание замен и обмен секретным ключом между всеми сторонами.
Этот метод использовался для создания подстановки в приведенном выше примере. В качестве ключевых слов было использовано греческое предложение: timeo Danaos et dona ferentes.
Одной из характеристик простых подстановочных шифров является то, что разные буквы алфавита открытого текста всегда будут давать разные буквы зашифрованного текста. Невозможно, чтобы оба они были зашифрованы одной и той же буквой алфавита.
Безопасность простых подстановочных шифров
Поскольку каждый символ может быть закодирован любой буквой алфавита, их 26! возможные пары букв латинского алфавита (который состоит из 26 букв). В результате получается большое количество комбинаций. Обеспечиваемая безопасность примерно равна стойкости шифра с секретным ключом размером 88 бит.
Однако гораздо более эффективный подход, чем атаки методом перебора, состоит в использовании частотного анализа букв зашифрованного текста для взлома простого шифра подстановки.Буквы на всех языках появляются в средних текстах с разной частотой. Таким образом, гораздо быстрее обнаруживать замены, используемые в шифре, сравнивая частые буквы зашифрованного текста с буквами, которые часто используются в языке, используемом для шифрования. При использовании этого подхода предполагается, что анализа закодированных сообщений размером около 50 букв достаточно для обнаружения замен.
Моноалфавитный шифр замещения — онлайн-декодер криптограмм, решатель
Поиск инструмента
Моно-алфавитная замена
Инструмент для расшифровки одноалфавитной замены и поиска каждой буквы замененного сообщения с нарушенным алфавитом (одноалфавитный шифр).
Результаты
Моно-алфавитная замена — dCode
Тег (и): Замещающий шифр
Поделиться
dCode и другие
dCode является бесплатным, а его инструменты являются ценным подспорьем в играх, математике, геокешинге, головоломках и задачах, которые нужно решать каждый день!
Предложение? обратная связь? Жук ? идея ? Запись в dCode !
Декодер одноалфавитной подстановки
Моноалфавитный кодировщик замены
Генератор нестандартных ненормальных алфавитов
Ответы на вопросы (FAQ)
Как зашифровать с помощью алфавитной подстановки?
Моноалфавитная замена состоит в использовании смешанного алфавита (с буквами в необычном порядке) и замене им букв обычного алфавита.
Пример: NBAJYFOWLZMPXIKUVCDEGRQSTH — это полностью случайный алфавит из 26 букв латинского алфавита.
Чтобы понять, напишите алфавит над классическим алфавитом:
| Обычный алфавит | ABCDEFGHIJKLMNOPQRSTUVWXYZ |
|---|---|
| Замена алфавита | NBAJYFOWLZMPXIKUVCDEGRQSTH |
| Замещающий алфавит | NBAJYFOWLZMPXIKUVCDEGRQSTH |
|---|---|
| Обычный алфавит | ABCDEFGHIJKLMNOPQRSTUVWXYZ |
= 99 99 = |
Выход:
Шифрованный текст: M eq wxyhCmrk Hexe IrgvCtxmsr Восстановленный простой текст: я изучаю шифрование данных
Внимание компьютерщик! Укрепите свои основы с помощью курса Python Programming Foundation и изучите основы.
Для начала подготовьтесь к собеседованию. Расширьте свои концепции структур данных с помощью курса Python DS . И чтобы начать свое путешествие по машинному обучению, присоединяйтесь к курсу Машинное обучение - базовый уровень
Замещающие шифры
- истоки и приложения криптографии
Возможно, мы привыкли думать о шифровании как о современном цифровом явлении. Но люди отправляли закодированные передачи в той или иной форме, в значительной степени с тех пор, как был изобретен язык.
Одной из наиболее широко используемых форм ранней криптографии был шифр замещения.
Что такое шифры замещения?
Замещающий шифр - это метод криптографии (наука о написании, анализе и расшифровке кодов), который преобразует стандартный язык или открытый текст в кодированный язык или зашифрованный текст путем замены единиц открытого текста в соответствии с фиксированным набором правил. Эти единицы открытого текста могут быть отдельными буквами или символами, парами букв, тройками или другими комбинациями.
Замещающие шифры могут заменять зашифрованным текстом только буквы стандартного алфавита, а также применять замены к пробелам и знакам препинания.
Простые подстановочные шифры (или одноалфавитные подстановочные шифры)
Простые или одноалфавитные шифры замещения основаны на отображении отдельных букв алфавита открытого текста на конкретную букву алфавита зашифрованного текста.
Для простой замены каждая буква стандартного алфавита заменяется той же буквой или символом зашифрованного текста в соответствии с фиксированным правилом.Так, например, если в закодированном сообщении буква «а» должна быть заменена символом «#», такая же замена будет происходить в каждом сообщении, закодированном в соответствии с этим конкретным правилом замены.
Поскольку каждая буква стандартного алфавита теоретически может быть заменена любой другой буквой или символом, существует бесконечное количество потенциальных моноалфавитных шифров замещения. При ручном кодировании проще всего сначала создать алфавит зашифрованного текста, а затем выполнить шифрование, сравнивая его с алфавитом открытого текста.
Генераторы ключевых слов
Популярный метод, используемый при создании алфавитов зашифрованного текста для простой подстановки, заключается в том, чтобы начать с ключевого слова - предпочтительно слова, в котором каждая буква стандартного алфавита встречается только один раз (например, «запас» или «каюта»). Это слово помещается в начало таблицы, а оставшиеся буквы алфавита помечаются в конце в их обычном порядке (т.е. пропускают те буквы, которые встречаются в ключевом слове).
Шифр Атбаша
Один из первых записанных шифров подстановки, шифр Атбаша, вводил моноалфавитные замены в еврейском алфавите.Это была простая система, в которой каждый отрывок открытого текста, который был закодирован, использовал один и тот же алфавит зашифрованного текста.
Шифр Атбаша создал свой алфавит зашифрованного текста, просто перевернув алфавит открытого текста, сопоставив первую букву стандартного алфавита с последней, вторую - со второй последней и так далее. Система получила свое название фонетически от замены еврейского «алеф» его зашифрованной формой «тав» и «бет» на «шин».
Естественно, этот метод может быть применен к любому языковому алфавиту и является быстрым и простым инструментом для сокрытия сообщений некритической важности от глаз случайных наблюдателей.К методике может быть применен элемент дополнительной безопасности путем пометки строки чисел, символов или знаков препинания в конце алфавита зашифрованного текста перед выполнением замен.
Шифр Цезаря
Немного более безопасным, чем Атбаш, был шифр сдвига, который использовал Юлий Цезарь для отправки зашифрованных сообщений своим армиям в полевых условиях. Сдвиг или шифр Цезаря работает, сдвигая алфавит на заданное количество ходов и заменяя каждую букву открытого текста ее эквивалентом смещенного зашифрованного текста.В Древнем Риме Цезарь заменил букву «а» на букву «д» - «сдвиг на 3», что по сути создало ключ шифрования для языка.
Итак, приняв решение о номере смены, создание алфавита зашифрованного текста является относительно простым делом сдвига букв стандартного алфавита на согласованное количество разрядов влево. Это дает «d» в качестве первой буквы алфавита Цезаря Шифра, за которой следует «efgh» и т. Д. С буквами «abc», добавленными после «z». Шифрование исходного сообщения происходит простой заменой букв на соответствующий зашифрованный текст.
Расшифровка зашифрованного текста может быть выполнена путем обращения к таблице смещенного алфавита, созданной для шифрования сообщения, или путем создания новой таблицы, которая смещает стандартные буквы алфавита на такое же количество позиций в противоположном направлении.
Шифр Свиньи (Шифр масонов)
Этот шифр подстановки заменяет каждую букву алфавита открытого текста соответствующим символом. Хотя его историческое происхождение неясно, шифр Свиньи на протяжении многих лет использовался несколькими группами, в частности, в том числе солдатами Союза, заключенными в тюрьму Конфедерацией во время Гражданской войны в США, и полусекретным обществом масонов 18-го века.
Масоны использовали шифр «Свиной пень» во многих аспектах своей повседневной жизни и даже при смерти: криптографические сообщения были обнаружены на надгробных надписях предполагаемых членов общества.
Сетка символов создана для создания «алфавита» зашифрованного текста, и каждая буква закодированного сообщения просто сопоставляется и заменяется назначенным ей символом.
Подстановочные шифры диграфа
В отличие от моноалфавитных шифров замещения, шифры замещения диграфов заменяют пары букв стандартного алфавита парой букв зашифрованного текста.
Сообщение в виде открытого текста сначала разбивается на пары букв или диграфов. Пары замещения могут быть определены с использованием комбинации моноалфавитных методов, таких как два сдвига Цезаря. Первый сдвиг будет применяться к первой букве каждой пары, а второй сдвиг диктует вторую букву.
Взлом кода
Несмотря на их успех в исторических приложениях, простые, моноалфавитные и подстановочные шифры с диграфом довольно легко взломать при наличии времени и надлежащих методов.
Грубой силы (проб и ошибок) может быть достаточно, чтобы взломать шифр Цезаря Shift, поскольку существует только 26 возможных алфавитов зашифрованного текста, которые используют все стандартные буквы.
В других случаях применение высококлассного процесса, называемого частотным анализом, может взломать код. Этот относительно простой метод включает просмотр фрагмента зашифрованного текста с заменой букв в соответствии с известными правилами, регулирующими использование стандартного языка: наиболее часто встречающиеся буквы («e» на английском языке), общие слова («the», «and» ) и аналогичные условия могут дать правильное начальное представление о содержимом сообщения.Некоторые обоснованные догадки могут быть использованы для заполнения оставшихся пробелов.
Полиалфавитные шифры замещения
Из-за этих присущих недостатков были предприняты попытки разработать более сильные коды замены. Примерно в 1467 году Леон Баттиста Альберти создал первый известный полиалфавитный шифр замещения. Шифр Альберти использовал смешанный алфавит для шифрования, который переключался на другой алфавит зашифрованного текста в случайных точках текста. Эти точки были отмечены в коде заглавной буквой.Альберти закодировал ключи к этой системе на наборах шифровальных дисков.
Основываясь на работе Альберти, разнообразная группа, включая немецкого монаха Йоханнеса Тритемиуса, итальянского ученого Джованни Порта и, в частности, французского дипломата 16 века Блеза де Виженера, переработала полиалфавитную замену в шифр Виженера, в котором в полной мере использовалось до 26 различных зашифрованных текстов. алфавитах и оставался до 1854 года как «Le Chiffre Undechiffrable» или «Нерушимый шифр».
Современные приложения
Конечно, даже самый надежный код замены не выдержит пяти минут интенсивного взлома с использованием современных технологий.Но хотя эти методы никоим образом не являются достаточно безопасными для современных приложений, они открыли путь для развития современных методов шифрования и криптографического анализа.
Некоторые ресурсы
Если вы хотите попробовать свои силы в шифровании некоторых сообщений с помощью подстановочных шифров, есть бесплатные документы с упражнениями, которые вы можете скачать с разных сайтов.
Online вы также найдете возможности протестировать шифр Виженера и узнать, как его и другие подстановочные шифры взламывать.
Резюме
Название статьи
Шифры замещения - истоки и приложения криптографии
Описание
Шифры замещения преобразуют стандартный язык или открытый текст в кодированный язык или зашифрованный текст путем замены текста в соответствии с фиксированным набором правил.
Автор
Финджан
Имя издателя
Finjan
Логотип издателя
Онлайн-калькулятор: инструмент шифрования замены
Этот простой инструмент позволяет кодировать и декодировать сообщения с помощью простого шифра замены.Для взломщика шифров см. Подстановочный шифр-декодер. Вы можете прочитать описание шифра и некоторые соображения относительно надежности шифра под калькулятором.
Substitution Cipher Tool
БЕГАТЬ СРАЗУ. МЫ ОБНАРУЖЕНЫ Создание пятибуквенных групп HNGGC VQPEG YGCTG FKUEQ XGTGFCA TR GE YW FD KI нас EC QO XV PN VT Ссылка Сохранить Виджет
Согласно Википедии, в криптографии подстановочный шифр - это метод шифрования, при котором единицы открытого текста заменяются зашифрованным текстом в соответствии с фиксированной системой; «единицы» могут быть отдельными буквами (наиболее распространенными), парами букв, тройками букв, смесями вышеперечисленного и так далее.Получатель расшифровывает текст, выполняя обратную замену.
Простая замена - это замена отдельных букв по отдельности. Ключ подстановки обычно представлен записью алфавита в определенном порядке. Шифр Цезаря - это форма простого шифра подстановки. Например, его ключ ROT2 может быть представлен как CDEFGHIJKLMNOPQRSTUVWXYZAB. Это означает, что A заменяется на C, B на D и так далее.
Количество всех возможных ключей для простого шифра подстановки - это факториал 26 (26!).Однако вы можете взломать его, если у вас достаточно зашифрованного текста, используя частотный анализ или алгоритм стохастической оптимизации (посмотрите наш декодер шифрования подстановки). В отличие, например, от полиалфавитного шифра Виженера, шифр не изменяет частоту языковых букв (он называется моноалфавитным), поэтому считается довольно слабым.
Вставьте текст в поле, заполните ключ, выберите «закодировать», если вы вставили чистый текст, или «декодировать», если вы вставили зашифрованный текст, и нажмите «Рассчитать».