Как закалялась сталь современной симметричной криптографии. Глава 2. Математическая криптография
https://habr.com/ru/articles/728908/
3.7KИнформационная безопасность*Криптография*Программирование*C*Математика*Ретроспектива
Введение
Современные симметричные шифры, которыми мы пользуемся неявно, но повсеместно, появились в ходе своей многовековой эволюции, в ходе продолжительных и постоянных этапов собственного совершенствования. Каждый новый шаг улучшения приводил одновременно к разрушению старых уязвимых шифров и к порождению новых, более качественных и безопасных. Тем не менее, само разрушение старых алгоритмов всегда двояко свидетельствовало как об их недостатках, которые необходимо было искоренять, так и об их достоинствах, которые нужно было наследовать. В следствие этого, каждый новый, более качественный шифр, представлял собой количественный синтез старых, менее качественных алгоритмов шифрования.
Данная статья является логическим продолжением первой главы, в которой разбирались шифры классической криптографии, а также их классификация. Если вы уже знакомы с классической криптографией, понимаете её основы, то скорее всего вам и не нужно будет предисловие в виде первой главы. Тем не менее, если классическая криптография вам неизвестна или существуют белые пятна, то могу порекомендовать сначала прочитать первую главу, потому как в текущей статье мы попытаемся из классических, ранее изученных "деталей" создавать их математические модели.
Материал может быть полезен как преподавателям предмета КСЗИ, так и непосредственно студентам при изучении классической и современной криптографии. Ровно также как в первой главе, к разбираемым шифрам (и не только) я буду прикладывать программные реализации на языке программирования Си. В конце данной статьи также будет указан небольшой список литературы по математической криптографии, с которым вы сможете ознакомиться.
Математическая криптография
Под математической криптографией мы будем подразумевать промежуточную стадию между классической и современной криптографией. Можно сказать, что математическая криптография, в неком роде, становится основным двигателем, основным способом перерождения криптографии из искусства (классической формы) в науку (современную форму). Тем не менее, если исходить из строгой классификации обобщённой криптографии, как совокупности всего изученного, то математическая криптография не будет представлять собой отдельную дисциплину изучения, потому как таковая относится в большей мере к современной криптографии, чем к классической, и как следствие не может выступать как самодостаточная стадия развития криптографии.
Основное же противоречие классификации математической криптографии начинает наблюдаться в том факте, что само математическое описание шифров рождается в эпоху классической криптографии и плавно "перетекает" в современную. Так например, первые способы математического представления шифра Виженера датируются ещё 1888 годом, французом маркиз де Виари, Хилл представил шифр, базируемый полностью на алгебраических матрицах в 1929 году, в то время как рождение современной криптографии начинается примерно со второй половины XX века, начиная с работ Шеннона. Из этого следует, что математическая криптография совмещает в себе не только описание современной криптографии, но и классической. На основе всего вышеперечисленного можно сделать вывод, что математическую криптографию действительно нельзя рассматривать как отдельную дисциплину изучения (наравне с классической или современной криптографией), но следует рассматривать как некий "мостик", позволяющий переходить из классической криптографии в современную. Такое качество для нас как раз и является необходимым в определении того, как создавались современные симметричные алгоритмы шифрования.
В данной работе не будут затрагиваться математические определения вне контекста симметричной криптографии, как например, эллиптические кривые, задача дискретного логарифмирования, задача факторизации, односторонние функции и т.д. Но при этом стоит сказать, что далее изученное может помочь в понимании алгебраических тем не только связанных с симметричной криптографии, но и связанных с асимметричной криптографией, потому как даже асимметричные алгоритмы шифрования (и даже в большей мере асимметричные алгоритмы шифрования) описываются математическими моделями.
Алгебраическая модель шифров
Любое симметричное шифрование может быть представлено в виде формулы C = EK(M), где E - функция шифрования, K - ключ шифрования, M - открытый текст, C - закрытый текст. Функцию шифрования также можно представить как отображение множества открытых текстов на множество закрытых: EK: M⇒C. Расшифрование соответственно будет представлено как обратная функция EK-1 к шифрованию EK, и как следствие, получается дополнительная формула вида M = EK-1(C). Расшифрование можно представить как отображение множества закрытых текстов на множество открытых: EK-1: C⇒M. Из этого также следует, что M = EK-1(EK(M)), то-есть применяя функцию шифрования, а затем функцию расшифрования, мы всегда будем получать оригинальное сообщение - открытый текст. Такое слияние функций может быть представлено как композиция функций EK-1*EK = I, где I - тождественная функция I(M) = M. В дальнейшем, под обратной функцией шифрования - расшифрованием, мы будем понимать функцию DK = EK-1, для более лёгкого обозначения (E = Encrypt, D = Decrypt).
Более формально, шифр можно представить как совокупность введённых множеств ∑(M, K, C, E, D) для которых выполняются следующие свойства:
- Dk(Ek(m))=m для (любых) ∀m∈M, ∀k∈K. Иными словами, для любого открытого текста m из множества всех сообщений M и любого ключа k из множества всех ключей K всегда будет выполняться равенство Dk(Ek(m)) = m.
- C=⋃Ek(m). Иными словами, объединение всех множеств шифрования по k и m приводит ко всему множеству шифрованных сообщений C.
Стоит также заметить, что в формальном математическом описании функции E и D представляют собой не как таковые функции, а именно множества всех возможных отображений шифрования / расшифрования, в то время как k представляет собой выбор конкретного отображения из множеств E и D соотвественно. Например, в шифре Цезаря мы можем представить: 1) E как функцию шифрования от аргумента k вида Ek(m) = m+k; 2) E как множество отображений вида {E1, E2, ..., En}, где k становится выбором отображения.
Из первого свойства следует свойство инъективности шифрования. Другими словами, если (существуют) ∃m1,m2∈M, где m1≠m2, то при (любых) ∀k∈K, выполняется неравенство Ek(m1) ≠ Ek(m2). И действительно, если пойти от обратного и предположить, что существует такое равенство Ek(m1) = Ek(m2) при m1≠m2, то функция расшифрования будет приводить к неоднозначному отображению множества C на множество M при помощи ключа k, в результате чего само расшифрование станет неоднозначным.
При этом стоит сказать, что сама инъективность расшифрования необязательна. Например, если (существуют) ∃c1,c2∈C, где c1≠c2, то может (существовать) ∃k∈K, который приведёт к равенству Dk(c1) = Dk(c2) = m. Это можно наблюдать на примере омофонических шифров, где при Ek(m) мы можем получить c1 ИЛИ c2 с определёнными вероятностями p1 И p2 соответственно. Связано это в первую очередь с тем, что сам ключ k представлен списком множеств, ориентируемых на сообщение m. Более простыми словами, выбор ключа k начинает базироваться не только на основе всего множества K, но и на выборе конкретного сообщения m.
Из второго свойства следует свойство сюръективности. Так например, для (любых) ∀c∈C, ∀k∈K (существует) ∃m∈M, такое что Ek(m)=c. Иными словами, каждый шифртекст c из множества C имеет отображение в открытый текст m из множества M. Если шифр инъективный при расшифровании, тогда он также является биективным шифром, потому как свойства инъективности при шифровании и сюръективности априори присутствуют в математической модели шифра.
В действительности же, в истории криптографии существовали модели несюръективных шифров, при которых (не существует) ∄ci∈C для равентства ci=Ek(mi). Так например, несюръективным шифром мог выступать шифр простой подстановки с ложными символами, где некоторые шифртексты ci (ложные символы) могли не иметь отображения в mi. Тем не менее, таковой механизм шифрования является избыточным и несамостоятельным в том простом плане, что ложные символы сами по себе являются способом запутывания при криптоанализе и не представляют собой алгоритм шифрования.
Получив общую математическую модель шифрования / расшифрования, нам становится возможным выводить последующие свойства при определённых алгоритмах шифрования.
- Свойство инволютивности. Функция шифрования равна функции расшифрования: EK = DK, и как следствие, применяя дважды шифрование или расшифрование мы будем получать открытый текст M = DK(EK(M)) = EK(EK(M)) = DK(DK(M)) = EK(DK(M)).
- Свойство коммутативности. Порядок применения функций шифрования и/или расшифрования не имеет значения: Ek*DK=Dk*EK, и как следствие, DK(EK(M)) = EK(DK(M)) = M, или: Ek1*Ek2=Ek2*EK1, и как следствие, EK1(EK2(M)) = EK2(EK1(M)) = C (аналогично с расшифрованием).
- Свойство биективности. При (любых) ∀k∈K, ∀m∈M результатом шифрования становится одно единственное отображение Ek(m) = c. Иными словами, при шифровании некого открытого текста m с определённым ключом k существует ровно один закрытый текст c.
- Свойство ассоциативности. При (любых) ∀k1,k2∈K, ∀m∈M результатом шифрования или расшифрования становится преобразование двух ключей над входным сообщением. Иными словами, Ek1(Ek2(m)) = Eq(m), где q=Ek1(k2). Если принять за функцию шифрования E операцию #, то такое действие можно описать более наглядным способом: m#(k1#k2) = (m#k1)#k2.
В качестве примера инволютивного шифра может выступать шифр Цезаря с ключом k=13 (ROT13) для английского алфавита. С любым другим k шифр Цезаря не является инволютивным. Также, в качестве примера полностью инволютивного шифра может выступать парный шифр и xor-шифрование (операция Исключающее ИЛИ).
В качестве примера коммутативного шифра может выступать также шифр Цезаря, потому как Dk(Ek(m)) = (m+k)-k = (m-k)+k = Ek(Dk(m)) = m. В качестве некоммутативного шифра может выступать шифр Порты по причине разного формата данных между открытым и закрытым текстами.
В качестве примера биективного шифра может выступать также шифр Цезаря, потому как отображение Ek(m) = c задаёт единственный результат c от k и m. В качестве примера небиективного шифра может выступать омофонический шифр, где для одного m и k могут выступать разные ci из множества Cmk = {c1, c2, ..., cn}.
В качестве примера ассоциативного шифра может аналогично выступать шифр Цезаря, потому как: Ek2(Ek1(m)) = (m+k1)+k2 = m+(k1+k2) = Eq(m), где q = Ek1(k2).
Таким образом, в качестве примера вышеописанных свойств, шифр Цезаря представляет собой коммутативный и биективный шифр. Но при этом инволютивность шифра Цезаря существует лишь при отображении E13 для английского алфавита.
Модели шифров классической криптографии
Изучив основы алгебраических моделей шифров, мы можем приступать к более практическому их применению. За основу мы возьмём шифры классической криптографии и попробуем представить их классы и подклассы в виде алгебраических моделей.
Представим сообщение m как последовательность символов m1, m2, m3, ..., mn.
Подстановочные шифры EK(M) = C ⇒ ⋃{ci}.
- Моноалфавитный шифр: Ek(m1), Ek(m2), Ek(m3), ..., Ek(mn), где k∈K - ключ шифрования, применяемый к каждому символу mi независимо. Ключ k статичен, не зависит ни от позиции шифруемого символа mi, ни от его уникальных характеристик (частот встречаемости, композиции символов и т.д).Пример. Существует алфавит, как упорядоченное множество, A=(ABCDE), состоящий лишь и только из пяти символов, и сообщение m=(ACBA). Ключом примем отображение k: A ⇒ B на определённый алфавит B=(QWERT), такое что k(mi) = BfA(mi), где fA - функция вычисления нумерации элемента m в A. Таким образом, Ek(mi) = BfA(mi).
Результат: A=Q, B=W, C=E, D=R, E=T, шифртекст c = Ek(ACBA) = (QEWQ). - Омофонический шифр: Er(k)(m1), Er(k)(m2), Er(k)(m3), ..., Er(k)(mn), где k∈K - ключ шифрования, применяемый к каждому символу mi∈M независимо через функцию случайного выбора применяемого подключа r из k на mi. Ключ k не зависит от позиции шифруемого символа mi, но зависит от его уникальных характеристик, посредством функции r.Пример. Существует алфавит, как упорядоченное множество, A=(ABCDE), состоящий лишь и только из пяти символов, и сообщение m=(ACBA). Ключом примем отображение k: A ⇒ B на определённое упорядоченное множество неупорядоченных множеств B=({QW}{E}{R}{T}{Y}), такое что k(mi) = r(BfA(mi)), где fA - функция вычисления нумерации элемента m в A, r - функция случайного выбора элемента из неупорядоченного множества. Таким образом, Ek(mi) = r(BfA(mi)).Результат: A=Q или A=W, B=E, C=R, D=T, E=Y, шифртекст (вероятностно может быть таким) c = Ek(ACBA) = (QREW).
- Полиалфавитный шифр: EГ1(m1), EГ2(m2), EГ3(m3), ..., EГn(mn), где Гi - ключевая гамма, генерируемая из ключа k∈K, и применяемая к каждому символу mi независимо. Гамма Гi не зависит от его уникальных характеристик, но при этом зависит от позиции шифруемого символа mi. В отличие от других подстановочных шифров, где ключ всегда предполагает вычисление нумерации элемента в упорядоченном множестве, гамма в полиалфавитных шифрах "оторвана" от такой модели и генерируется полностью независимо от характеристик сообщения m и его порядка в алфавите A.Пример. Существует алфавит, как упорядоченное множество, A=(ABCDE), состоящий лишь и только из пяти символов, и сообщение m=(ACBA). Ключом примем генерацию гаммы по формуле k(i) = Гi = i mod 3, что эквивалентно шифру Виженера с ключом k=BCD, если нумерация начинается с единицы. Таким образом, Ek(mi) = (k(i)+mi) mod |A|.Результат: шифртекст c = Ek(ACBA) = (BEBB).
- Полиграммный шифр: Ek(m1, m2, ..., mq), Ek(mq+1, mq+2, ..., m2q), Ek(m2q+1, m2q+2, ..., m3q), ..., Ek(m(n-1)q+1, m(n-1)q+2, ..., mnq), где k∈K - ключ шифрования, применяемый к группе символов Ek(m(n-1)q+1, m(n-1)q+2, ..., mnq) независимо. Ключ k статичен, не зависит ни от позиции шифруемой группы символов m(n-1)q+1, m(n-1)q+2, ..., mnq, ни от её уникальных характеристик.Пример. Существует алфавит, как упорядоченное множество, A=(ABCDE), состоящий лишь и только из пяти символов, и сообщение m=(ACBA). Ключом примем отображение k: A ⇒ B на определённый алфавит B=(QWERT...), такое что k(m(n-1)q+1, m(n-1)q+2, ..., mnq) = BfA(m(n-1)q+1, m(n-1)q+2, ..., mnq), где fA - функция вычисления нумерации группы элементов (m(n-1)q+1, m(n-1)q+2, ..., mnq) в A. Таким образом, Ek(m(n-1)q+1, m(n-1)q+2, ..., mnq) = BfA(m(n-1)q+1, m(n-1)q+2, ..., mnq).
Результат (биграммный шифр): AC=W, BA=G, CA=X, DE=A, ..., шифртекст c = Ek(ACBA) = (WG).
Необходимо принять во внимание тот факт, что результатом отображения в B может быть разное количество элементов. Например, шифр Плейфера отображает биграмму на биграмму, шифр Порты отображает биграмму на триграмму (если брать количество цифр в качестве символов), шифр Хилла отображает N-грамму на N-грамму. В нашем примере, шифр отображает биграмму на одиночный символ, что в представленных реалиях вполне возможно, т.к. при мощности множества A (количестве элементов множества), |A|=5 ⇒ всего существует 52=25 отображений. Поэтому необходимо иметь лишь 25 символов для отображения всех биграмм. - Коды: Ek(m1, m2, ..., mq), Ek(mq+1, mq+2, ..., mq+w), Ek(mq+w+1, mq+w+2, ..., mq+w+e), ..., Ek(mq+w+e+...+r+1, mq+w+e+...+r+2, ..., mq+w+e+...+r+t), где k∈K - ключ шифрования, применяемый к группе символов Ek(m(n-1)q+1, m(n-1)q+2, ..., mnq) независимо. Ключ k статичен, не зависит ни от позиции шифруемой группы символов m(n-1)q+1, m(n-1)q+2, ..., mnq, ни от её уникальных характеристик. В отличие от шифров полиграммной подстановки, коды располагают динамическим размером блоков, где q, w, e, ..., r, t могут быть как равны, так и неравны между собой.Пример. Существует алфавит, как упорядоченное множество, A=(ABCDE), состоящий лишь и только из пяти символов, и сообщение m=(ACBAEAC). Ключом примем отображение k: A ⇒ B на определённый алфавит B=(QWERT...), такое что k(m(n-1)q+1, m(n-1)q+2, ..., mnq) = BfA(m(n-1)q+1, m(n-1)q+2, ..., mnq), где fA - функция вычисления нумерации группы элементов (m(n-1)q+1, m(n-1)q+2, ..., mnq) в A. Таким образом, Ek(m(n-1)q+1, m(n-1)q+2, ..., mnq) = BfA(m(n-1)q+1, m(n-1)q+2, ..., mnq).
Результат: ACBA=Q, EAC=R, шифртекст c = Ek(ACBAEAC) = (QR).
Перестановочные шифры EK(M) = C ⇒ ⋃{mi}.
- Простая перестановка: Ek(m1, m2, ..., mq), Ek(mq+1, mq+2, ..., m2q), Ek(m2q+1, m2q+2, ..., m3q), ..., Ek(m(n-1)q+1, m(n-1)q+2, ..., mnq), где Ek(m1, m2, ..., mnq) ⇒ {m1, m2, ..., mnq}.Пример. Существует алфавит, как упорядоченное множество, A=(ABCDE), состоящий лишь и только из пяти символов, и сообщение m=(ACBAEE). Ключом примем отображение k: A ⇒ A, такое что k(m(n-1)q+1, m(n-1)q+2, ..., mnq) = P(m(n-1)q+1, m(n-1)q+2, ..., mnq), где P - функция перестановки элементов в группе (m(n-1)q+1, m(n-1)q+2, ..., mnq). Таким образом, Ek(m(n-1)q+1, m(n-1)q+2, ..., mnq) = P(m(n-1)q+1, m(n-1)q+2, ..., mnq). Примем ключевую перестановку P = (213).
Результат: ACB=CAB, AEE=EAE, BCA=CBA, ..., шифртекст c = Ek(ACBAEE) = (CABEAE).
Таким образом, на базе общей алгебраической модели шифрования мы смогли выразить более конкретизированную алгебраическую модель, направленную на описание классических алгоритмов шифрования.
Примеры шифров классической криптографии
В данном разделе мы попробуем выразить математическим языком некоторые алгоритмы шифрования классической криптографии. Для анализа возьмем следующие:
Таковой список был выбран по причине их похожести (для подстановочных), но и при этом "разношёрстности". Данное противоречие позволит нам 1) Легко адаптироваться под новый алгоритм шифрования, исходя из ранее изученных шифров, 2) Удобно выявлять новые направления, а также изменения анализируемого алгоритма шифрования в сравнении с ранее изученными.
1. Шифр Цезаря
Данный алгоритм шифрования описывается по достаточно лёгкой формуле: Ek(m) = mi+k ≡ ci (mod n). Расшифрование соответственно выглядит похожим образом: Dk(c) = ci-k ≡ mi (mod n). Сообщение и ключ представляются как числа. При этом под разные сообщения mi, а также шифртексты ci используется один и тот же ключ k.
В приведённой выше формуле нас может заинтересовать применение конструкции (mod n), а также специфичный знак ≡ (тождество). В общем случае таковые элементы взаимосвязаны. Начнём пожалуй с определения (mod n). mod - это деление по модулю, или более простыми словами - деление с остатком.
Модульной арифметикой называют алгебраические правила действующие на определённые выражения при использовании операции mod. Работу таковой операции легко можно продемонстрировать на следующем примере:
В такой концепции можно сказать, что mod - это не только остаток от деления, но и некого рода зацикленность перебираемых элементов. В нашем примере, (mod 3) образует постоянно множество из трёх элементов вида {0, 1, 2}, какие бы целые числа на вход не подавались. В более общем виде, образуемое множество при делении по модулю n можно представить как {0, 1, 2, ..., n-1} (mod n).
При этом, стоит заметить, что любые элементы большие чем n в k раз будут зацикливаться и попадать всегда во множество модуля n. Так например,
- {0n, 1n, 2n, ..., kn, ...} ≡ 0 (mod n),
- {0n+1, 1n+1, 2n+1, ..., kn+1, ...} ≡ 1 (mod n),
- {0n+2, 1n+2, 2n+2, ..., kn+2, ...} ≡ 2 (mod n),
- ...,
- {0n+(n-1), 1n+(n-1), 2n+(n-1), ..., kn+(n-1), ...} ≡ (n-1) (mod n).Таковые порождаемые множества называются классами вычетов. Каждое множество из классов вычетов является бесконечным множеством. В итоге, любой элемент классов вычетов может быть представлен как kn+x ≡ x (mod n).
Стоит также заметить тот факт, что модульная арифметика производит операции не над множеством натуральных чисел N, а над множеством целых чисел Z. Это говорит о том, что могут существовать выражения типа -x (mod n). Такие выражения достаточно легко интерпретируются. Так например, -1 ≡ 4 (mod 5), -2 ≡ 3 (mod 5), -3 ≡ 2 (mod 5), -4 ≡ 1 (mod 5), -5 ≡ 0 (mod 5), -6 ≡ -1 ≡ 4 (mod 5), ... Иными словами, отрицательные числа в конечных кольцах становятся априори положительными, базируясь на формуле -x = (n > kn-x ⩾ 0).
На основе всего вышесказанного, выражение вида kn+x = ln+x становится не эквивалентным, исходя из разности элементов в классах вычетов. Таким образом, используя операцию эквивалентности само выражение становится неравенством kn+x ≠ ln+x. Тем не менее, использование модульной арифметики приводит к иным результатам и к тождественности выражений kn+x ≡ ln+x ≡ x (mod n).
В результате всего этого, модульная арифметика создаёт конечное кольцо Zn, которое обладает следующими свойствами:
- Коммутативность. a + b ≡ b + a (mod n), для (всех) ∀a,b∈Zn
- Ассоциативность. (a + b) + c ≡ a + (b + c) (mod n), для (всех) ∀a,b,c∈Zn
- Дистрибутивность. c(a + b) ≡ ca + cb (mod n), для (всех) ∀a,b,c∈Zn
- Нулевой элемент 0. a + 0 = 0 + a ≡ a (mod n), для (всех) ∀a∈Zn (существует) ∃0∈Zn
- Противоположный элемент (-a). a + (-a) = (-a) + a ≡ 0 (mod n), для (всех) ∀a∈Zn (существует) ∃(-a)∈Zn
Исходя из всего вышеописанного можно сказать, что любая операция шифра Цезаря совершается в конечном кольце Zn, и как следствие, при любой операции будут соблюдаться все свойства конечных колец. Это легко продемонстрировать на следующих примерах:
- Коммутативность. 8 + 21 = 21 + 8 ≡ 3 (mod 26)
- Ассоциативность. (8 + 21) + 5 = 8 + (21 + 5) ≡ 8 (mod 26)
- Дистрибутивность.
3 * (8 + 21) = 3*29 = 87 ≡ 9 (mod 26)
3 * (8 + 21) = 3*8 + 3*21 = 24 + 63 ≡ 24 + 11 ≡ 9 (mod 26) - Нулевой элемент. 8 + 0 ≡ 0 + 8 ≡ 8 (mod 26)
- Противоположный элемент.
8 + (-8) = (-8) + 8 ≡ 0 (mod 26)
8 + (-8) ≡ 8 + (26-8) ≡ 8 + 18 ≡ 0 (mod 26)
Программная реализация шифра Цезаря
#include "encoder.h"
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
typedef struct caesar_t {
encoder_t *encoder;
int32_t key;
} caesar_t;
extern caesar_t *caesar_new(encoder_t *encoder, int32_t k);
extern void caesar_free(caesar_t *caesar);
extern uint8_t *caesar_encrypt(caesar_t *caesar, uint8_t *output, uint8_t *input);
extern uint8_t *caesar_decrypt(caesar_t *caesar, uint8_t *output, uint8_t *input);
static uint8_t *encrypt_string(caesar_t *caesar, encmode_t m, uint8_t *output, uint8_t *input);
static int32_t encrypt_code(encoder_t *encoder, int32_t c, int32_t k);
int main(int argc, char *argv[]) {
uint8_t alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
uint8_t size_alph = (uint8_t)strlen((char*)alphabet);
encoder_t *encoder = encoder_new(size_alph);
encoder_set_alphabet(encoder, alphabet);
uint8_t message[BUFSIZ];
uint32_t key = 3;
strcpy((char*)message, "HELLOWORLD");
caesar_t *caesar = caesar_new(encoder, key);
printf("%s\n", (char*)caesar_encrypt(caesar, message, message));
printf("%s\n", (char*)caesar_decrypt(caesar, message, message));
caesar_free(caesar);
encoder_free(encoder);
return 0;
}
extern caesar_t *caesar_new(encoder_t *encoder, int32_t k) {
caesar_t *caesar = (caesar_t*)malloc(sizeof(caesar_t));
caesar->encoder = encoder;
caesar->key = k;
return caesar;
}
extern void caesar_free(caesar_t *caesar) {
free(caesar);
}
extern uint8_t *caesar_encrypt(caesar_t *caesar, uint8_t *output, uint8_t *input) {
return encrypt_string(caesar, MODE_ENC, output, input);
}
extern uint8_t *caesar_decrypt(caesar_t *caesar, uint8_t *output, uint8_t *input) {
return encrypt_string(caesar, MODE_DEC, output, input);
}
static uint8_t *encrypt_string(caesar_t *caesar, encmode_t m, uint8_t *output, uint8_t *input) {
size_t input_len = strlen((char*)input);
int encoded_ch, encrypted, flag;
for (int i = 0; i < input_len; i++) {
encoded_ch = encoder_encode(caesar->encoder, input[i], &flag);
if (flag == 0) {
fprintf(stderr, "undefined char %c;\n", input[i]);
return NULL;
}
encrypted = encrypt_code(caesar->encoder, encoded_ch, m*caesar->key); // m = {-1, 1}
output[i] = encoder_decode(caesar->encoder, encrypted, &flag);
if (flag == 0) {
fprintf(stderr, "undefined code %c;\n", encrypted);
return NULL;
}
}
output[input_len] = '\0';
return output;
}
static int32_t encrypt_code(encoder_t *encoder, int32_t c, int32_t k) {
uint8_t size = encoder_get_size_alphabet(encoder);
return (c+k+size)%size;
}2. Шифр Виженера
Данный алгоритм шифрования очень схож с шифром Цезаря. Тем не менее, особенность сводится к применению ключа в виде набора чисел. Следовательно, само шифрование шифром Виженера описывается как Ek(m) ≡ mi+ki (mod n). В шифре Виженера также существует условность при которой, если длина ключа меньше длины сообщения, то таковой ключ дублируется до длины сообщения. Исходя из этой условности можно дополнить формулу шифрования: Ek(m) ≡ mi+k(i mod q) (mod n), где q - размер ключа. Расшифрование выглядит соответствующе как Dk(c) ≡ ci-k(i mod q) (mod n).
Программная реализация шифра Виженера
#include "encoder.h"
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
typedef struct vigenere_t {
encoder_t *encoder;
uint8_t *key;
uint32_t key_size;
} vigenere_t;
extern vigenere_t *vigenere_new(encoder_t *encoder, uint8_t *key);
extern void vigenere_free(vigenere_t *vigenere);
extern uint8_t *vigenere_encrypt(vigenere_t *vigenere, uint8_t *output, uint8_t *input);
extern uint8_t *vigenere_decrypt(vigenere_t *vigenere, uint8_t *output, uint8_t *input);
static uint8_t *encrypt_string(vigenere_t *vigenere, encmode_t m, uint8_t *output, uint8_t *input);
static int32_t encrypt_code(encoder_t *encoder, int32_t c, int32_t k);
int main(int argc, char *argv[]) {
uint8_t alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
uint8_t size_alph = (uint8_t)strlen((char*)alphabet);
encoder_t *encoder = encoder_new(size_alph);
encoder_set_alphabet(encoder, alphabet);
uint8_t message[BUFSIZ];
uint8_t key[] = "QWE";
strcpy((char*)message, "HELLOWORLD");
vigenere_t *vigenere = vigenere_new(encoder, key);
printf("%s\n", (char*)vigenere_encrypt(vigenere, message, message));
printf("%s\n", (char*)vigenere_decrypt(vigenere, message, message));
vigenere_free(vigenere);
encoder_free(encoder);
return 0;
}
extern vigenere_t *vigenere_new(encoder_t *encoder, uint8_t *key) {
vigenere_t *vigenere = (vigenere_t*)malloc(sizeof(vigenere_t));
vigenere->encoder = encoder;
vigenere->key_size = strlen((char*)key);
vigenere->key = (uint8_t*)malloc(sizeof(uint8_t)*vigenere->key_size+1);
strcpy((char*)vigenere->key, (char*)key);
return vigenere;
}
extern void vigenere_free(vigenere_t *vigenere) {
free(vigenere->key);
free(vigenere);
}
extern uint8_t *vigenere_encrypt(vigenere_t *vigenere, uint8_t *output, uint8_t *input) {
return encrypt_string(vigenere, MODE_ENC, output, input);
}
extern uint8_t *vigenere_decrypt(vigenere_t *vigenere, uint8_t *output, uint8_t *input) {
return encrypt_string(vigenere, MODE_DEC, output, input);
}
static uint8_t *encrypt_string(vigenere_t *vigenere, encmode_t m, uint8_t *output, uint8_t *input) {
size_t input_len = strlen((char*)input);
int encoded_ch, encrypted, key, flag;
for (int i = 0; i < input_len; i++) {
encoded_ch = encoder_encode(vigenere->encoder, input[i], &flag);
if (flag == 0) {
fprintf(stderr, "undefined char %c;\n", input[i]);
return NULL;
}
key = encoder_encode(vigenere->encoder, vigenere->key[i%vigenere->key_size], &flag);
if (flag == 0) {
fprintf(stderr, "encode key char %c;\n", vigenere->key[i%vigenere->key_size]);
return NULL;
}
encrypted = encrypt_code(vigenere->encoder, encoded_ch, m*key); // m = {-1, 1}
output[i] = encoder_decode(vigenere->encoder, encrypted, &flag);
if (flag == 0) {
fprintf(stderr, "undefined code %c;\n", encrypted);
return NULL;
}
}
output[input_len] = '\0';
return output;
}
static int32_t encrypt_code(encoder_t *encoder, int32_t c, int32_t k) {
uint8_t size = encoder_get_size_alphabet(encoder);
return (c+k+size)%size;
}
3. Шифр Тритемиуса
Данный шифр представляет собой полиалфавитный алгоритм шифрования, где ключом становится некая функция. Данная функция принимает в качестве аргумента позицию шифруемого символа. Формула шифрования: Ek(m) ≡ mi+k(i) (mod n). Расшифрование выполняется аналогичным образом: Dk(c) ≡ ci-k(i) (mod n). В отличие от шифра Виженера, где ключ постоянно дублировался, шифр Тритемиуса представляет более сложную концепцию генерации ключа (гаммы). Так например, предположим, что в качестве языка по-умолчанию был выбран английский, тогда размер алфавита n=26. Ключом будет являться следующая функция k(i) = 2i+1, сообщением m = HELLO = (7,4,11,11,14) (кодирование сообщения по принципу A=0, B=1, C=2, ..., X=23, Y=24, Z=25).
c1 ≡ 7+(2*1+1) (mod 26) = 10 = K
c2 ≡ 4+(2*2+1) (mod 26) = 9 = J
c3 ≡ 11+(2*3+1) (mod 26) = 18 = S
c4 ≡ 11+(2*4+1) (mod 26) = 20 = U
c5 ≡ 14+(2*5+1) (mod 26) = 25 = Z
В итоге, мы получим сообщение KJSUZ. При расшифровании используется тот же самый алгоритм генерации гаммы, изменяется лишь операция со сложения на вычитание.
Программная реализация шифра Тритемиуса
#include "encoder.h"
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
typedef struct trithemius_t {
encoder_t *encoder;
uint8_t (*f_key)(uint32_t i);
} trithemius_t;
extern trithemius_t *trithemius_new(encoder_t *encoder, uint8_t (*f_key)(uint32_t i));
extern void trithemius_free(trithemius_t *trithemius);
extern uint8_t *trithemius_encrypt(trithemius_t *trithemius, uint8_t *output, uint8_t *input);
extern uint8_t *trithemius_decrypt(trithemius_t *trithemius, uint8_t *output, uint8_t *input);
static uint8_t *encrypt_string(trithemius_t *trithemius, encmode_t m, uint8_t *output, uint8_t *input);
static int32_t encrypt_code(encoder_t *encoder, int32_t c, int32_t k);
uint8_t f_key(uint32_t i) {
return 2*i+1;
}
int main(int argc, char *argv[]) {
uint8_t alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
uint8_t size_alph = (uint8_t)strlen((char*)alphabet);
encoder_t *encoder = encoder_new(size_alph);
encoder_set_alphabet(encoder, alphabet);
uint8_t message[BUFSIZ];
strcpy((char*)message, "HELLOWORLD");
trithemius_t *trithemius = trithemius_new(encoder, f_key);
printf("%s\n", (char*)trithemius_encrypt(trithemius, message, message));
printf("%s\n", (char*)trithemius_decrypt(trithemius, message, message));
trithemius_free(trithemius);
encoder_free(encoder);
return 0;
}
extern trithemius_t *trithemius_new(encoder_t *encoder, uint8_t (*f_key)(uint32_t i)) {
trithemius_t *trithemius = (trithemius_t*)malloc(sizeof(trithemius_t));
trithemius->encoder = encoder;
trithemius->f_key = f_key;
return trithemius;
}
extern void trithemius_free(trithemius_t *trithemius) {
free(trithemius);
}
extern uint8_t *trithemius_encrypt(trithemius_t *trithemius, uint8_t *output, uint8_t *input) {
return encrypt_string(trithemius, MODE_ENC, output, input);
}
extern uint8_t *trithemius_decrypt(trithemius_t *trithemius, uint8_t *output, uint8_t *input) {
return encrypt_string(trithemius, MODE_DEC, output, input);
}
static uint8_t *encrypt_string(trithemius_t *trithemius, encmode_t m, uint8_t *output, uint8_t *input) {
size_t input_len = strlen((char*)input);
int encoded_ch, encrypted, flag;
for (int i = 0; i < input_len; i++) {
encoded_ch = encoder_encode(trithemius->encoder, input[i], &flag);
if (flag == 0) {
fprintf(stderr, "undefined char %c;\n", input[i]);
return NULL;
}
encrypted = encrypt_code(trithemius->encoder, encoded_ch, m*f_key(i+1)); // m = {-1, 1}
output[i] = encoder_decode(trithemius->encoder, encrypted, &flag);
if (flag == 0) {
fprintf(stderr, "undefined code %c;\n", encrypted);
return NULL;
}
}
output[input_len] = '\0';
return output;
}
static int32_t encrypt_code(encoder_t *encoder, int32_t c, int32_t k) {
uint8_t size = encoder_get_size_alphabet(encoder);
return (c+(k%size)+size)%size;
}
4. Аффинный шифр
Данный шифр представляет собой моноалфавитную замену и является общим случаем шифра Цезаря. В отличие от последнего, Аффинный шифр базируется не на конечных кольцах Zn, а на мультипликативных группах конечных колец Zn*. Таковая специфичная группа определяет в конечном кольце единичный элемент, операцию умножения и обратный элемент, но при этом не каждый элемент множества Zn может соответствовать операциям из Zn*. Когда мощность (количество элементов) множества Zn\{0} (за исключением нуля) равно количеству элементов во множестве Zn*, тогда n является простым числом, а мультипликативное кольцо Zn* становится конечным полем Fq.
Конечные поля мы будем обозначать как Fq. Возьмём конечные поля за основу дальнейшего повествования. Когда потребуется необходимость в операциях умножения над модулем составного (не простого) числа, мы будем в явном виде использовать Zn*.
Простым числом называют такое число, которое делится только на единицу и на само себя. Например, число 7 является простым числом, потому как не существует более никаких делителей кроме единицы и семи. Число 9 не является простым числом, потому как помимо делителей единицы и девяти существует также делитель - три.
Примеры простых чисел до 100: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Конечное поле Fq обладает всеми свойствами конечного кольца Zq и свойствами коммутативной мультипликативной группы G<*, 1>.
- Коммутативность. ab ≡ ba (mod n), для (всех) ∀a,b∈Fq
- Ассоциативность. a(bc) ≡ (ab)c (mod n), для (всех) ∀a,b,c∈Fq
- Единичный элемент 1. a1 = 1a ≡ a (mod n), для (всех) ∀a∈Fq (существует) ∃1∈Fq
- Обратный элемент a-1. aa-1 = a-1a ≡ 1 (mod n), для (всех) ∀a∈Fq (существует) ∃a-1∈Fq
Коммутативность, ассоциативность и единичный элемент знакомы многим по причине их постоянного использования в обычной арифметике / алгебре с начальных-средних классов. Тем не менее, обратный элемент в конечных полях представляет собой более сложную вещь, хоть и определение такого обратного элемента нам также давно известно из вычислений на множестве рациональных чисел: a-1=1/a. Основная сложность вычисления заключается в том, что в конечных полях не может существовать дробных чисел, а следовательно и обратное число a-1 мы не можем представить как 1/a.
Примеры обратных элементов к числу 7 в конечных полях F29, F127, F131.
- 7 * a-1 ≡ 1 (mod 29) ⇒ a-1 = 25 ⇒ 7 * 25 = 175 ≡ 1 (mod 29)
- 7 * a-1 ≡ 1 (mod 127) ⇒ a-1 = 109 ⇒ 7 * 109 = 763 ≡ 1 (mod 127)
- 7 * a-1 ≡ 1 (mod 131) ⇒ a-1 = 75 ⇒ 7 * 75 = 525 ≡ 1 (mod 131)
И на этом моменте у многих людей, изучающих криптографию, но плохо знакомых с модульной арифметикой, начинается стагнация в изучении. И действительно, вычисление обратного элемента в конечном поле не такая простая задача, как вычисление этого же обратного элемента на бесконечном множестве рациональных чисел. Ситуация ещё усложняется тем фактом, что если выбрана мультипликативная группа конечного кольца Zn*, а не конечно поле Fq, то для некоторых элементов может и вовсе не существовать обратных чисел. Так например, для числа 6 по модулю 26 не существует обратного элемента, но при этом для числа 3 обратный элемент существует и равен 9, т.к. 3*9 = 27 ≡ 1 (mod 26).
Существование или несуществование обратных элементов определяется наибольшим общим делителем (НОД) равным единице, что говорит о взаимной простоте двух чисел. Наибольший общий делитель (НОД) может быть вычислен посредством алгоритма Евклида и описан в виде рекуррентной функции.
НОД(a, b) = a, если b = 0 НОД(a, b) = НОД(b, a mod b)
Так например, НОД(88, 52) = НОД(52, 88 mod 52 = 36) = НОД(36, 52 mod 36 = 16) = НОД(16, 36 mod 16 = 4) = НОД(4, 16 mod 4 = 0) = 4. Это может говорить о том, что не существует обратного элемента для числа 88 по модулю 52, ровно как и не существует обратного элемента для числа 52 по модулю 88, т.к. результат НОД приводит к четырём (то есть число 4 - это наибольший общий делитель чисел 52 и 88 соответственно).
Связь наибольшего общего делителя с определением существования обратных чисел связан непосредственно с коэффициентами в расширенном алгоритме Евклида, о котором речь пойдёт далее, по ходу повествования.
uint64_t gcd (uint64_t a, uint64_t b) {
if (b == 0) {
return a;
}
return gcd(b, a%b);
}uint64_t gcd(uint64_t a, uint64_t b) {
uint64_t t;
while (b != 0) {
t = a % b;
a = b;
b = t;
}
return a;
}При этом стоит сказать, что сама задача вычисления обратного элемента не является вычислительно сложной, что говорит о существовании эффективного или эффективных алгоритмов решения. Существует два способа нахождения обратного элемента вне концепций полного перебора.
Малая теорема Ферма
Является самым простым способом нахождения обратного числа по модулю простого числа. Недостатком является тот факт, что малая теорема Ферма не может находить обратные числа по модулю составного числа.
Малая теорема Ферма выражается формулой ap-1 ≡ 1 (mod p), где p - простое число, а число a - натуральное число не имеющее общих делителей с p ⇒ НОД(a, p) = 1, где НОД - наибольший общий делитель.
Доказательство малой теоремы Ферма
Если НОД(a, p)=1, то множество {1a, 2a, 3a, ..., (p-2)a, (p-1)a} (mod p) будет равно множеству {1, 2, 3, ..., p-2, p-1} (mod p), т.к. любое ka будет некратно числу p, вследствие чего не может существовать остатка равногонулю, т.е.не может существовать тождества вида ka ≡ 0 (mod p).
Остаётся доказать лишь то, что для любых k, a и l (mod p), где a≠l, остаётся справедливым неравенство ka≠kl. Пойдём от обратного и предположим, что при a≠l может существовать тождество ka ≡ la (mod p), тогда ka-la ≡ (k-l)a ≡ 0 (mod p), но это невозможно, т.к. для любого (k-l) должно быть справедливо нетождество (k-l) ≢0 (mod p).
Следовательно, т.к. никакой элемент ka не может быть равен нулю и никакой элемент не совпадает для всех k неравных друг другу, то и само получаемое множество становится {1a, 2a, 3a, ..., (p-2)a, (p-1)a} (mod p) не только равным по количеству (мощности) множеству {1, 2, 3, ..., p-2, p-1} (mod p), но и полностью равно ему.
Из всего этого также следует, что 1*2*3*...*(p-2)*(p-1) ≡ 1a*2a*3a*...*(p-2)a*(p-1)a (mod p). Это же выражение можно записать в более простом виде: ap-1(p-1)! ≡ (p-1)! (mod p), где (!) - факториал.
Мы можем сократить полученное выражение на (p-1)!, лишь при условии существования (p-1)!-1, следовательно НОД((p-1)!, p) должен быть равен единице. Т.к. все элементы {1, 2, 3, ..., p-2, p-1} не кратны p, то и их произведение будет не кратно p, что и приводит к существованию (p-1)!-1 (mod p).
Применяем сокращение: ap-1(p-1)!(p-1)!-1 ≡ (p-1)!(p-1)!-1 ≡ 1 (mod p), получаем выражение: ap-1 ≡ 1 (mod p), что и требовалось доказать.
Малая теорема Ферма часто применяется в вероятностных методах нахождения больших простых чисел. Тем не менее, нам важно применение данной теоремы для нахождения обратных чисел. И так, одним из следствий малой теоремы Ферма становится тождество: a*ap-2 = ap-1 ≡ 1 (mod p). В таком следствии, обратным элементом для a становится число равное a-1=ap-2. Таким образом, всё что нам остаётся - это вычислить операцию возведения в степень. Пример.
7 * 7-1 ≡ 1 (mod 29)
7-1 ≡ 729-2 = 727 ≡ 1 (mod 29)
7-1 ≡ 7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7 ≡ 25 (mod 29)
7 * 25 ≡ 1 (mod 29)
Тем не менее, присутствует во всём этом также проблема в плане эффективности вычисления больших степеней. Так например вычислить степень вида 359334085968622831041960188598043661065388726959079835 будет большой проблемой при наивном и последовательном умножении числа на само себя. В таком случае, применяют алгоритм быстрого возведения в степень. Его работу можно описать в виде следующего псевдокода.
Вход: x=число, y=степень, n=модуль (не обязательно простой)
Выход: r=результат возведения в степень
Алгоритм:
r = 1
y = (yn)(yn-1)(yn-2)...(y3)(y2)(y1) (y представляется в битовом виде)
Для всех y от 1 до n
Если yi = 1
r = r*x mod n
x = x*x mod n
Вернуть rТак в качестве примера, возьмём n=199, x=5, y=117. При обычном возведении в степень нам необходимо было бы совершить 116 операций умножения. Увеличение числа y приводило бы прямо пропорционально к увеличению совершаемых операций. Иными словами, образовалась бы линейно зависимая связь O(N). Тем не менее, в алгоритме быстрого возведения в степень, сложность самого вычисления составляет O(log2N). Т.к. y=117, где 26<y<27, то для полного возведения в степень потребуется всего 7 итераций, потому как ⌈log2117⌉=7, и максимум 14 операций умножения, потому как каждая итерация максимум может содержать две операции умножения. Пример.
Программная реализация быстрого возведения в степень
extern uint64_t expmod(uint64_t x, uint64_t y, uint64_t n) {
uint64_t r = 1;
for (uint64_t bit = 1; bit <= y; bit <<= 1) {
if (bit & y) {
r = (r * x) % n;
}
x = (x * x) % n;
}
return r;
}r=1 | x=5 | y=117 | n=199
y=11101012
1. y1=1 | r=(1*5) mod 199=5 | x=52 mod 199=25
2. y1=0 | x=252 mod 199=28
3. y1=1 | r=(5*28) mod 199=140 | x=282 mod 199=187
4. y1=0 | x=1872 mod 199=144
5. y1=1 | r=(140*144) mod 199=61 | x=1442 mod 199=40
6. y1=1 | r=(61*40) mod 199=52 | x=402 mod 199=8
7. y1=1 | r=(52*8) mod 199=18 (последнюю операцию x2 можно не писать)
Таким образом, в качестве результата выражения 5117 mod 199 мы получили число 18. Правильность выполнения мы можем проверить либо на калькуляторе, либо на определённом онлайн ресурсе, как например тут.
Программная реализация малой теормы Ферма для нахождения обратных чисел
extern uint64_t inv_number(uint64_t a, uint64_t p) {
// p обязано быть простым числом!
return expmod(a, p-2, p);
}Расширенный алгоритм Евклида
Под расширенным алгоритмом Евклида понимается не только способ нахождения НОД, но и способ нахождения неких коэффициентов x, y для входных чисел a, b. Расширенный алгоритм Евклида имеет следующую формулу: ax + by = НОД(a, b). Иными словами, любой НОД от двух чисел может быть представлен в виде линейной формулы ax + by.
Применение расширенного алгоритма Евклида при нахождении обратных чисел определяется следующими возможными действиями.
ax + by = НОД(a, b)
Если числа a, b - взаимнопросты (не имеют общих делителей), то НОД(a, b) = 1.
В следствие этого, формула обретает новый вид:
ax + by = 1
Теперь, если все операции производятся по модулю b, тогда число by становится равным нулю (т.к. любое число y в формуле by (mod b) будет равно нулю):
ax + by ≡ ax ≡ 1 (mod b)
Из этого следует, что само число x является обратным числом к a:
x ≡ a-1 (mod b).
Алгоритм для нахождения коэффициентов сводится к следующим действиям псевдокода:
Вход: a=число, b=число
Выход: d=НОД(a,b), x=коэффициент, y=коэффициент
Алгоритм:
x0 = 1, x1 = 0
y0 = 0, y1 = 1
Пока b не равен 0
q = a / b
r = a mod b
xi = x0 - q * x1
yi = y0 - q * y1
a = b
b = r
x0 = x1
x1 = xi
y0 = y1
y1 = yi
Вернуть a, x0, y0В более математическом виде, действия расширенного алгоритма Евклида сводятся к итеративному применению двух основных формул.
- a = bq + r, где q - делитель, r - остаток от деления.
- xi = xi-2 - qi-2 * xi-1. Данная формула полностью совпадает и для коэффициента y.
Можно привести следующий пример работы расширенного алгоритма Евклида для двух чисел: a = 24, b = 101.
1. 24 = 101 * 0 + 24, a = 24, b = 101, q = 0, r = 24
2. 101 = 24 * 4 + 5, a = 101, b = 24, q = 4, r = 5
3. 24 = 5 *4 + 4, a = 24, b = 5, q = 4, r = 4
4. 5 = 4 *1 + 1, a = 5, b = 4, q = 1, r = 1
5. 4 = 1 *4 + 0. a = 4, b = 1, q = 4, r = 0
Как только r становится равен 0, то результатом вычисления становится b. Таким образом, НОД(a, b) = 1. Вышеописанное - это обычный алгоритм Евклида. Тем не менее, в расширенном алгоритме Евклида нам необходим не как таковой НОД в качестве результата, а именно делители q для вычисления коэффициентов x и y непосредственно.
1. x0 = 1,
2. x1 = 0,
3. x2 = 1 - 0 * 0 = 1 (q0 = 0)
4. x3 = 0 - 4 * 1 = -4 (q1 = 4)
5. x4 = 1 - 4 * -4 = 17 (q2 = 4)
6. x5 = -4 - 1 * 17 = -21 (q3 = 1)
В результате мы получаем, что x5 ≡ a-1 (mod 101), т.к. a * x5 = 24 * (-21) = -504 ≡ 1 (mod 101). Мы бы также могли найти коэффициент y, но это было бы бессмысленно, если нашей целью является нахождение обратного числа a-1 по модулю b, т.к. yb (mod b) ≡ 0.
Программная реализация расширенного алгоритма Евклида для нахождения обратных чисел
extern uint64_t inv_number(uint64_t a, uint64_t b) {
uint64_t tx = 0, x0 = 1, x1 = 0;
uint64_t q = 0, r = 0;
uint64_t tb = b;
while (b != 0) {
q = a / b;
r = a % b;
tx = x0 - q * x1;
a = b;
b = r;
x0 = x1;
x1 = tx;
}
return (x0 + tb) % tb;
}Таким образом, зная и понимая всё вышеперечисленное, мы можем приступать к рассмотрению самого Аффинного шифра. Функция шифрования в Аффинном шифре определяется как Ek(m) ≡ (ami+b) (mod n), где k = (a, b). Расшифрование представляет собой последовательное применение обратных элементов (-b) и (a-1) непосредственно: Dk(c) ≡ a-1(ci-b) (mod n). Из всего этого следует, что число a должно быть взаимнопростым с число n, чтобы существовало обратное число a-1, иными словами НОД(a, n) = 1. Если a=1, то обратное число a-1 также равно 1, вследствие чего формулы упрощаются до Ek(m) ≡ mi+b (mod n) и Dk(c) ≡ ci-b (mod n), где Аффинный шифр переводится в шифр Цезаря.
В качестве примера предположим, что сообщение m=5, a=4, b=8, n=29, тогда процесс шифрования сводится к следующим действиям: (4*5+8) ≡ 28 (mod 29). Основная сложность возникает на этапе расшифрования, потому как необходимым действием становится вычисление обратного числа 4-1 по модулю 29. В данном контексте мы можем воспользоваться либо расширенным алгоритмом Евклида (как наиболее универсальным средством нахождения обратных чисел), либо малой теоремой Ферма (потому как число 29 - это простое число). В результате мы получим 4-1 ≡ 22 (mod 29). И действительно, 4*22 = 88 ≡ 1 (mod 29). Теперь, всё что нам остаётся - это применить формулу расшифрования: 22*(28-8) = 440 ≡ 5 (mod 29).
Программная реализация Аффинного шифра
#include "encoder.h"
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
typedef struct aphine_t {
encoder_t *encoder;
int32_t key_a;
int32_t key_b;
} aphine_t;
extern aphine_t *aphine_new(encoder_t *encoder, uint32_t key_a, uint32_t key_b);
extern void aphine_free(aphine_t *aphine);
extern uint8_t *aphine_encrypt(aphine_t *aphine, uint8_t *output, uint8_t *input);
extern uint8_t *aphine_decrypt(aphine_t *aphine, uint8_t *output, uint8_t *input);
extern uint64_t gcd(uint64_t a, uint64_t b);
extern uint64_t inv_number(uint64_t a, uint64_t b);
static uint8_t *encrypt_string(aphine_t *aphine, encmode_t m, uint8_t *output, uint8_t *input);
static int32_t encrypt_code(encoder_t *encoder, int32_t c, int32_t key_a, int32_t key_b);
static int32_t decrypt_code(encoder_t *encoder, int32_t c, int32_t key_a, int32_t key_b);
int main(int argc, char *argv[]) {
uint8_t alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
uint8_t size_alph = (uint8_t)strlen((char*)alphabet);
encoder_t *encoder = encoder_new(size_alph);
encoder_set_alphabet(encoder, alphabet);
uint8_t message[BUFSIZ];
strcpy((char*)message, "HELLOWORLD");
aphine_t *aphine = aphine_new(encoder, 3, 7);
printf("%s\n", (char*)aphine_encrypt(aphine, message, message));
printf("%s\n", (char*)aphine_decrypt(aphine, message, message));
aphine_free(aphine);
encoder_free(encoder);
return 0;
}
extern aphine_t *aphine_new(encoder_t *encoder, uint32_t key_a, uint32_t key_b) {
uint8_t size = encoder_get_size_alphabet(encoder);
if (gcd(key_a, size) != 1) {
return NULL;
}
aphine_t *aphine = (aphine_t*)malloc(sizeof(aphine_t));
aphine->encoder = encoder;
aphine->key_a = key_a;
aphine->key_b = key_b;
return aphine;
}
extern void aphine_free(aphine_t *aphine) {
free(aphine);
}
extern uint8_t *aphine_encrypt(aphine_t *aphine, uint8_t *output, uint8_t *input) {
return encrypt_string(aphine, MODE_ENC, output, input);
}
extern uint8_t *aphine_decrypt(aphine_t *aphine, uint8_t *output, uint8_t *input) {
return encrypt_string(aphine, MODE_DEC, output, input);
}
static uint8_t *encrypt_string(aphine_t *aphine, encmode_t m, uint8_t *output, uint8_t *input) {
size_t input_len = strlen((char*)input);
int encoded_ch, encrypted, flag;
for (int i = 0; i < input_len; i++) {
encoded_ch = encoder_encode(aphine->encoder, input[i], &flag);
if (flag == 0) {
fprintf(stderr, "undefined char %c;\n", input[i]);
return NULL;
}
switch (m) { // m = {-1, 1}
case MODE_ENC:
encrypted = encrypt_code(aphine->encoder, encoded_ch, aphine->key_a, aphine->key_b);
break;
case MODE_DEC:
encrypted = decrypt_code(aphine->encoder, encoded_ch, aphine->key_a, aphine->key_b);
break;
}
output[i] = encoder_decode(aphine->encoder, encrypted, &flag);
if (flag == 0) {
fprintf(stderr, "undefined code %c;\n", encrypted);
return NULL;
}
}
output[input_len] = '\0';
return output;
}
static int32_t encrypt_code(encoder_t *encoder, int32_t c, int32_t key_a, int32_t key_b) {
uint8_t size = encoder_get_size_alphabet(encoder);
return (key_a*c+key_b+size)%size;
}
static int32_t decrypt_code(encoder_t *encoder, int32_t c, int32_t key_a, int32_t key_b) {
uint8_t size = encoder_get_size_alphabet(encoder);
int32_t inv_key_a = inv_number(key_a, size);
return ((c-key_b+size)*inv_key_a+size)%size;
}
extern uint64_t gcd(uint64_t a, uint64_t b) {
uint64_t t;
while (b != 0) {
t = a % b;
a = b;
b = t;
}
return a;
}
extern uint64_t inv_number(uint64_t a, uint64_t b) {
uint64_t tx = 0, x0 = 1, x1 = 0;
uint64_t q = 0, r = 0;
uint64_t tb = b;
while (b != 0) {
q = a / b;
r = a % b;
tx = x0 - q * x1;
a = b;
b = r;
x0 = x1;
x1 = tx;
}
return (x0 + tb) % tb;
}
5. Шифр Хилла
Данный шифр представляет собой полиграммный алгоритм шифрования. Интересной особенностью данного алгоритма является ключ, представленный алгебраической матрицей. В отличие от шифра Порты или шифра Плейфера, которые являются только биграммными алгоритмами шифрования, шифр Хилла динамически полиграммный, в том простом смысле, что он может быть и биграммным, и триграммным, и т.д.
Функцию шифрования в шифре Хилла можно описать как EK(M) ≡ KM (mod n), где K - квадратная ключ-матрица, M - блок открытого текста. Блок открытого текста должен быть кратен размерности матрицы. Так например, если ключ-матрица K представлена как матрица 3x3, то само сообщение должно иметь размер кратный трём. Для успешного расшифрования необходимым действием становится нахождение обратной матрицы K-1, такой что DK(C) ≡ K-1C ≡ M (mod n).
Предположим, что у нас существует ключ-матрица K 3x3 следующего вида.
K =
[ 8 4 3]
[11 7 15]
[ 5 23 13]Первое, что нам необходимо сделать - это проверить, что для матрицы K существует обратная ей матрица K-1. Для этого необходимо проверить два условия, а именно, что detK≠0 и НОД(detK, n)=1, где detK - определитель матрицы K.
Определитель матрицы может быть вычислен через алгебраические дополнения Aij. Можно сказать, что существуют формулы проще, например через треугольники, но такое правило работает до тех пор, пока матрица размерности 3x3. Когда же матрица становится равной 4x4, 5x5 и т.д., то остаются лишь и только алгебраические дополнения.
Определитель матрицы вычисляется следующим образом: detK = a11A11+a12A12+...+a1nA1n., где aij - элемент матрицы, Aij - алгебраическое дополнение. Алгебраическое дополнение вычисляется по формуле Aij = (-1)i+jMij, где Mij - минор матрицы, выражаемый определителем матрицы меньшего порядка. Определитель матриц 2x2 вычисляется по следующей формуле: a11a22-a21a12.
Вычисление алгебраических дополнений
Алгебраическое дополнение вычисляется посредством вычёркивания строки и столбца, на которое само же алгебраическое дополнение указывает, приводя к меньшему порядку матрицы.
Так например, для A11 мы бы убрали первую строку и первый столбец матрицы, оставив тем самым только матрицу 2x2. На матрицу 2x2 применяется уже минор M11, который вычислит определитель матрицы, как 7*13-23*15.
И так, определитель матрицы detK вычисляется как 8*A11+4*A12+3*A13, где
A11 = (-1)1+1*(7*13-23*15) = -254,
A12 = (-1)1+2*(11*13-5*15) = -68,
A13 = (-1)1+3*(11*13-5*7) = 218.
Итого, detK = 8*(-254)+4*(-68)+3*218 = -1650 ≡ 3 (mod 29) ⇒ 3≠0 и НОД(3, 29)=1, значит обратная матрица существует. Если бы обратной матрицы не существовало, тогда нам необходимо было бы изменить либо саму матрицу K, либо модуль n.
Вычисление обратной матрицы сводится к двум действиям: 1) к вычислению обратного определителя матрицы, 2) к вычислению оставшихся алгебраических дополнений.
Обратный определитель матрицы мы можем легко вычислить либо по расширенному алгоритму Евклида, либо по малой теореме Ферма (т.к. n=29 - простое число). Для числа 3 обратным числом становится 3-1 ≡ 10 (mod 29), т.к. 3*10 ≡ 1 (mod 29).
Оставшиеся алгебраические дополнения вычисляются аналогичным образом, как и алгебраические дополнения при нахождении определителя матрицы.
A21 = (-1)2+1*(4*13-23*3) = 17,
A22 = (-1)2+2*(8*13-5*3) = 89,
A23 = (-1)2+3*(8*23-5*4) = -164,
A31 = (-1)3+1*(4*15-7*3) = 39,
A32 = (-1)3+2*(8*15-11*3) = -87,
A33 = (-1)3+3*(8*7-11*4) = 12.
Определив все алгебраические дополнения, необходимо теперь составить союзную матрицу A*. Союзная матрица в качестве своих элементов содержит алгебраические дополнения, но в транспонированном виде.
A* =
[A11 A21 A31]
[A12 A22 A32]
[A13 A23 A33]
=
[-254 17 39]
[ -68 89 -87]
[ 218 -164 12]
≡
[ 7 17 10]
[19 2 0]
[15 10 12] (mod 29)В конечном итоге, теперь мы можем вычислить обратную матрицу по следующей формуле: K-1=detK-1A*.
inv(K) = inv(detK)*(A*) =
[ 10*7 10*17 10*10]
[10*19 10*2 10*0]
[10*15 10*10 10*12]
=
[ 70 170 100]
[190 20 0]
[150 100 120]
≡
[12 25 13]
[16 20 0]
[ 5 13 4] (mod 29)Вычислив обратную матрицу мы теперь можем приступать к шифрованию и расшифрованию сообщений непосредственно. Предположим, что есть сообщение M=HDI, закодировав его, мы получим числа (7, 3, 8) (кодирование по принципу A=0, B=1, C=2, ..., X=23, Y=24, Z=25).
C = KM
[ 8 4 3][7]
[11 7 15][3]
[ 5 23 13][8]
=
[8*7 + 4*3 + 3*8]
[11*7 + 7*3 + 15*8]
[5*7 + 23*3 + 13*8]
=
[92]
[218]
[208]
≡
[5]
[15]
[5] (mod 29)Расшифрование выглядит аналогичным образом, только вместо K мы должны использовать обратную матрицу K-1.
M = inv(K)C
[12 25 13][5]
[16 20 0][15]
[ 5 13 4][5]
=
[12*5 + 25*15 + 13*5]
[16*5 + 25*15 + 0*5]
[5*5 + 13*15 + 4*5]
=
[500]
[380]
[240]
≡
[7]
[3]
[8] (mod 29)Программная реализация шифра Хилла
#include "encoder.h"
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
typedef struct hill_t {
encoder_t *encoder;
int32_t **matrix;
int32_t **inv_matrix;
uint8_t matrix_size;
} hill_t;
extern hill_t *hill_new(encoder_t *encoder, uint8_t matrix_size, int32_t **matrix);
extern void hill_free(hill_t *hill);
extern uint8_t *hill_encrypt(hill_t *hill, uint8_t *output, uint8_t *input);
extern uint8_t *hill_decrypt(hill_t *hill, uint8_t *output, uint8_t *input);
extern uint64_t gcd(uint64_t a, uint64_t b);
extern uint64_t inv_number(uint64_t a, uint64_t b);
static int32_t **matrix_new(uint8_t matrix_size);
static void matrix_free(int32_t **matrix, uint8_t matrix_size);
static uint8_t *encrypt_string(hill_t *hill, encmode_t m, uint8_t *output, uint8_t *input);
static int32_t math_mod(int32_t x, int32_t y);
static void mul_matrix_with_vector_mod(int32_t **matrix, int32_t matrix_size, int32_t *vector, int32_t mod);
static void mul_matrix_with_number_mod(int32_t **matrix, uint8_t matrix_size, int32_t number, int32_t mod);
static void set_algebraic_additions_mod(int32_t **out_matrix, int32_t **in_matrix, uint8_t matrix_size, int32_t mod);
static int32_t get_algebraic_addition(int32_t **in_matrix, uint8_t matrix_size, int32_t i, int32_t j);
static int32_t **get_minor(int32_t **in_matrix, uint8_t matrix_size, int32_t i, int32_t j, int32_t *res);
static int32_t get_determinant(int32_t **in_matrix, uint8_t matrix_size);
/*
[ 8 4 3]
[11 7 15]
[ 5 23 13]
*/
static void _fill_matrix(int32_t **matrix) {
matrix[0][0] = 8;
matrix[0][1] = 4;
matrix[0][2] = 3;
matrix[1][0] = 11;
matrix[1][1] = 7;
matrix[1][2] = 15;
matrix[2][0] = 5;
matrix[2][1] = 23;
matrix[2][2] = 13;
}
int main(int argc, char *argv[]) {
uint8_t alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ.,!";
uint8_t size_alph = (uint8_t)strlen((char*)alphabet);
encoder_t *encoder = encoder_new(size_alph);
encoder_set_alphabet(encoder, alphabet);
uint8_t message[BUFSIZ];
strcpy((char*)message, "HDI");
uint8_t matrix_size = 3;
int32_t **matrix = matrix_new(matrix_size);
_fill_matrix(matrix);
hill_t *hill = hill_new(encoder, matrix_size, matrix);
printf("%s\n", (char*)hill_encrypt(hill, message, message));
printf("%s\n", (char*)hill_decrypt(hill, message, message));
hill_free(hill);
matrix_free(matrix, matrix_size);
encoder_free(encoder);
return 0;
}
extern hill_t *hill_new(encoder_t *encoder, uint8_t matrix_size, int32_t **matrix) {
int32_t mod = encoder_get_size_alphabet(encoder);
int32_t det = get_determinant(matrix, matrix_size);
if (det == 0 || gcd(det, mod) != 1) {
return NULL;
}
hill_t *hill = (hill_t*)malloc(sizeof(hill_t));
hill->encoder = encoder;
hill->matrix_size = matrix_size;
hill->matrix = matrix_new(matrix_size);
hill->inv_matrix = matrix_new(matrix_size);
for (int i = 0; i < matrix_size; ++i) {
for (int j = 0; j < matrix_size; ++j) {
hill->matrix[i][j] = matrix[i][j];
}
}
set_algebraic_additions_mod(hill->inv_matrix, hill->matrix, matrix_size, mod);
mul_matrix_with_number_mod(hill->inv_matrix, matrix_size, inv_number(math_mod(det, mod), mod), mod);
return hill;
}
static int32_t math_mod(int32_t x, int32_t mod) {
return ((x%mod)+mod)%mod;
}
static void mul_matrix_with_vector_mod(int32_t **matrix, int32_t matrix_size, int32_t *vector, int32_t mod) {
int32_t orig_vector[matrix_size];
for (int i = 0; i < matrix_size; ++i) {
orig_vector[i] = vector[i];
}
for (int i = 0; i < matrix_size; ++i) {
int32_t s = 0;
for (int j = 0; j < matrix_size; ++j) {
s += math_mod(matrix[i][j]*orig_vector[j], mod);
}
vector[i] = math_mod(s, mod);
}
}
static void mul_matrix_with_number_mod(int32_t **matrix, uint8_t matrix_size, int32_t number, int32_t mod) {
for (int i = 0; i < matrix_size; ++i) {
for (int j = 0; j < matrix_size; ++j) {
matrix[i][j] = math_mod(matrix[i][j]*number, mod);
}
}
}
static void set_algebraic_additions_mod(int32_t **out_matrix, int32_t **in_matrix, uint8_t matrix_size, int32_t mod) {
for (int i = 0; i < matrix_size; ++i) {
for (int j = 0; j < matrix_size; ++j) {
// i,j => j,i: matrix transposition
out_matrix[j][i] = math_mod(get_algebraic_addition(in_matrix, matrix_size, i, j), mod);
}
}
}
// Здесь действительно достаточно сложная рекурсия нескольких связанных между собой функций.
// Так например, функция get_algebraic_addition вызывает get_minor, которая
// в свою очередь вызывает get_determinant. Эта функция в свою очередь
// вызывает вновь get_algebraic_addition, но с меньшим размером матрицы полученным из get_minor.
static int32_t get_algebraic_addition(int32_t **in_matrix, uint8_t matrix_size, int32_t i, int32_t j) {
int res;
int32_t **matrix = get_minor(in_matrix, matrix_size, i, j, &res);
matrix_free(matrix, matrix_size-1);
return (((i+j) % 2 == 0) ? 1 : -1) * res;
}
static int32_t **get_minor(int32_t **in_matrix, uint8_t matrix_size, int32_t i, int32_t j, int32_t *res) {
if (matrix_size <= 2) {
*res = get_determinant(in_matrix, matrix_size);
return NULL;
}
uint8_t minor_matrix_size = matrix_size-1;
int32_t **minor_matrix = (int32_t **)matrix_new(minor_matrix_size);
int32_t im = 0, jm = 0;
for (int _i = 0; _i < matrix_size; ++_i) {
if (_i == i) {
continue;
}
for (int _j = 0; _j < matrix_size; ++_j) {
if (_j == j) {
continue;
}
minor_matrix[im][jm] = in_matrix[_i][_j];
jm = (jm+1) % minor_matrix_size;
}
++im;
}
*res = get_determinant(minor_matrix, minor_matrix_size);
return minor_matrix;
}
static int32_t get_determinant(int32_t **in_matrix, uint8_t matrix_size) {
if (matrix_size < 2) {
return 0;
}
if (matrix_size == 2) {
return in_matrix[0][0]*in_matrix[1][1]-in_matrix[1][0]*in_matrix[0][1];
}
int32_t det = 0;
for (int i = 0; i < matrix_size; ++i) {
det += in_matrix[0][i]*get_algebraic_addition(in_matrix, matrix_size, 0, i);
}
return det;
}
extern void hill_free(hill_t *hill) {
matrix_free(hill->matrix, hill->matrix_size);
free(hill);
}
extern uint8_t *hill_encrypt(hill_t *hill, uint8_t *output, uint8_t *input) {
return encrypt_string(hill, MODE_ENC, output, input);
}
extern uint8_t *hill_decrypt(hill_t *hill, uint8_t *output, uint8_t *input) {
return encrypt_string(hill, MODE_DEC, output, input);
}
static uint8_t *encrypt_string(hill_t *hill, encmode_t m, uint8_t *output, uint8_t *input) {
uint8_t mod = encoder_get_size_alphabet(hill->encoder);
size_t input_len = strlen((char*)input);
int32_t encoded_ch, flag;
int32_t *vector = (int32_t*)malloc(sizeof(int32_t)*hill->matrix_size);
for (int i = 0; i < input_len; i += hill->matrix_size) {
for (int j = 0; j < hill->matrix_size; ++j) {
encoded_ch = encoder_encode(hill->encoder, input[i+j], &flag);
if (flag == 0) {
fprintf(stderr, "undefined char %c;\n", input[i]);
return NULL;
}
vector[j] = encoded_ch;
}
switch(m) {
case MODE_ENC:
mul_matrix_with_vector_mod(hill->matrix, hill->matrix_size, vector, mod);
break;
case MODE_DEC:
mul_matrix_with_vector_mod(hill->inv_matrix, hill->matrix_size, vector, mod);
break;
}
for (int j = 0; j < hill->matrix_size; ++j) {
output[i+j] = encoder_decode(hill->encoder, vector[j], &flag);
if (flag == 0) {
fprintf(stderr, "undefined char %c;\n", input[i]);
return NULL;
}
}
}
return output;
}
extern uint64_t gcd(uint64_t a, uint64_t b) {
uint64_t t;
while (b != 0) {
t = a % b;
a = b;
b = t;
}
return a;
}
extern uint64_t inv_number(uint64_t a, uint64_t b) {
uint64_t tx = 0, x0 = 1, x1 = 0;
uint64_t q = 0, r = 0;
uint64_t tb = b;
while (b != 0) {
q = a / b;
r = a % b;
tx = x0 - q * x1;
a = b;
b = r;
x0 = x1;
x1 = tx;
}
return (x0 + tb) % tb;
}
static int32_t **matrix_new(uint8_t matrix_size) {
int32_t **matrix = malloc(sizeof(int32_t*)*matrix_size);
for (int i = 0; i < matrix_size; ++i) {
matrix[i] = (int32_t*)malloc(sizeof(int32_t)*matrix_size);
}
return matrix;
}
static void matrix_free(int32_t **matrix, uint8_t matrix_size) {
for (int i = 0; i < matrix_size; ++i) {
free(matrix[i]);
}
free(matrix);
}
6. Шифры простой перестановки
Шифры простой перестановки чаще описываются более лёгким образом, чем подстановочные алгоритмы шифрования. По большей части это связано с простой математической моделью, базируемой на перестановках.
В идеальном случае, перестановочные шифры должны обладать b! возможным количеством ключей, где b - размер блока шифрования, с максимально возможным периодом d. Второе свойство является лишь желательным, потому как при его полном соблюдении теряется большое количество возможных ключей из b!.
Представим в качестве примера самую лёгкую перестановку, которая перемещает влево оригинальные символы текста. По большей части - это пример перестановки ключа в шифре Цезаря.
( 1 2 3 4 5 ) ( 2 3 4 5 1 ) = (1 2 3 4 5) [...->(1)->(2)->(3)->(4)->(5)->(1)->(2)->(3)->(4)->(5)->...]
На удивление, такая перестановка обладает наибольшим периодом d=5. Но стоит здесь конечно же сказать, что подобная перестановка представляет собой очень малую криптостойкость. Например, сообщение WORLD просто станет сообщением ORLDW. Такая слабая криптостойкость перестановки связана с большой линейностью (зависимостью) между открытым и закрытым текстом. Подобную линейность можно описать лишь одной формулой E(m) ≡ m+1 (mod n).
Попробуем теперь разобрать немного иную перестановку, случайно выбранную из всего множества ключей 5!.
( 1 2 3 4 5 ) ( 3 4 1 5 2 ) = (1 3)(2 4 5) [...->(1)->(3)->(1)->(3)->...] [...->(2)->(4)->(5)->(2)->(4)->(5)->...]
Данная перестановка не является качественной, потому как приводит к зависимостям нескольких символов друг от друга, что порождает малые периоды d=2 и d=3. Это говорит о том, что не каждая перестановка из всего множества 5! будет качественной, как первая нами представленная (конечно же в плане длины периоды, а не криптостойкости).
Малые периоды снижают криптостойкость в том простом плане, что первичная перестановка начинает делиться на несколько малых перестановок, из-за чего первичная длина ключа начинает ровно также делиться на несколько более малых ключей. Поэтому шифры простой перестановки играют на противоречии между количеством ключей и их качеством, ровно также, как это делают омофонические шифры.
Программная реализация шифра вертикальной перестановки
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
typedef struct vertical_permutation_t {
uint8_t *key;
uint8_t *sorted_key;
uint32_t key_size;
} vertical_permutation_t;
extern vertical_permutation_t *vertical_permutation_new(uint8_t *key);
extern void vertical_permutation_free(vertical_permutation_t *vertical_permutation);
extern uint8_t *vertical_permutation_encrypt(vertical_permutation_t *vertical_permutation, uint8_t *output, uint8_t *input);
extern uint8_t *vertical_permutation_decrypt(vertical_permutation_t *vertical_permutation, uint8_t *output, uint8_t *input);
static int find_index(uint8_t *arr, uint8_t v, int size);
static int comp(const void * elem1, const void * elem2);
int main(int argc, char *argv[]) {
uint8_t encrypted[BUFSIZ];
uint8_t message[BUFSIZ];
strcpy((char*)message, "HELLOWORLDXX");
uint8_t key[BUFSIZ];
strcpy((char*)key, "KEY");
vertical_permutation_t *vertical_permutation = vertical_permutation_new(key);
printf("%s\n", (char*)vertical_permutation_encrypt(vertical_permutation, encrypted, message));
printf("%s\n", (char*)vertical_permutation_decrypt(vertical_permutation, message, encrypted));
vertical_permutation_free(vertical_permutation);
return 0;
}
extern vertical_permutation_t *vertical_permutation_new(uint8_t *key) {
vertical_permutation_t *vertical_permutation = (vertical_permutation_t*)malloc(sizeof(vertical_permutation_t));
vertical_permutation->key_size = strlen((char*)key);
vertical_permutation->key = (uint8_t*)malloc(sizeof(uint8_t)*vertical_permutation->key_size+1);
vertical_permutation->sorted_key = (uint8_t*)malloc(sizeof(uint8_t)*vertical_permutation->key_size+1);
strcpy((char*)vertical_permutation->key, (char*)key);
strcpy((char*)vertical_permutation->sorted_key, (char*)key);
qsort(vertical_permutation->sorted_key, sizeof(uint8_t)*vertical_permutation->key_size, sizeof(uint8_t), comp);
return vertical_permutation;
}
extern void vertical_permutation_free(vertical_permutation_t *vertical_permutation) {
free(vertical_permutation->key);
free(vertical_permutation);
}
extern uint8_t *vertical_permutation_encrypt(vertical_permutation_t *vertical_permutation, uint8_t *output, uint8_t *input) {
size_t input_len = strlen((char*)input);
int index_key, output_i = 0;
if (input_len % vertical_permutation->key_size != 0) {
fprintf(stderr, "input_len %% vertical_permutation->key_size != 0");
return NULL;
}
for (int i = 0; i < vertical_permutation->key_size; ++i) {
index_key = find_index(vertical_permutation->key, vertical_permutation->sorted_key[i], vertical_permutation->key_size);
for (int j = index_key; j < input_len; j += vertical_permutation->key_size) {
output[output_i++] = input[j];
}
}
return output;
}
extern uint8_t *vertical_permutation_decrypt(vertical_permutation_t *vertical_permutation, uint8_t *output, uint8_t *input) {
size_t input_len = strlen((char*)input);
int index_key, output_i = 0;
if (input_len % vertical_permutation->key_size != 0) {
fprintf(stderr, "input_len %% vertical_permutation->key_size != 0");
return NULL;
}
for (int i = 0; i < input_len; i += vertical_permutation->key_size) {
for (int j = index_key; j < input_len; j += vertical_permutation->key_size) {
index_key = find_index(vertical_permutation->key, vertical_permutation->sorted_key[j], vertical_permutation->key_size);
output[output_i++] = input[j];
}
}
return output;
}
static int find_index(uint8_t *arr, uint8_t v, int size) {
for (int i = 0; i < size; ++i) {
if (arr[i] == v) {
return i;
}
}
return -1;
}
static int comp(const void * elem1, const void * elem2) {
uint8_t f = *((uint8_t*)elem1);
uint8_t s = *((uint8_t*)elem2);
if (f > s) return 1;
if (f < s) return -1;
return 0;
}Заключение
Математическая криптография на этом не заканчивается, потому как существует ещё очень много других тем, которые я не затронул или затронул, но на очень поверхностном уровне. Можно сказать, что приведённый выше материал представляет собой лишь основные моменты математической криптографии. Тем не менее, я попытался представить данный материал в наиболее доступной форме, со всеми возможными примерами.
Следующая глава станет финальной. В ней мы поговорим о математических моделях комбинаций и композиций алгоритмов шифрования и непосредственно о современных симметричных шифрах, об их структуре и схемах реализации. Всё это я постараюсь также сопровождать программными кодами на языке Си.
Список литературы
- Теория связи в секретных системах. К. Шеннон
- Основы криптографии. А. Алферов, А. Зубов, А. Кузьмин, А. Черемушкин
- Теоретико-числовые методы в криптографии. Е. Маховенко
- Современная криптография. Теория и практика. В. Мао
- Основы криптологии. Профессиональное руководство и интерактивный учебник. Х. Тилборг
- Современная дискретная математика. От перечислительной комбинаторики до криптографии XXI века. Ю. Зуев