Цель лекции: познакомиться с понятием "
Блочный алгоритм предназначен для шифрования блоков определенной длины. Однако может возникнуть необходимость шифрования данных не блоками, а, например, по символам. Поточный шифр (stream cipher) выполняет преобразование входного сообщения по одному биту (или байту) за операцию. Поточный алгоритм шифрования устраняет необходимость разбивать сообщение на целое число блоков достаточно большой длины, следовательно, он может работать в реальном времени. Таким образом, если передается поток символов, каждый символ может шифроваться и передаваться сразу.
Работа типичного поточного шифра представлена на рис 7.1.
(рис 7.1) Принцип работы поточного шифра
Генератор ключей выдает поток битов ki, которые будут использоваться в качестве гаммы. Источник сообщений генерирует биты открытого текста хi, которые складываются по модулю 2 с гаммой, в результате чего получаются биты зашифрованного сообщения уi:
Чтобы из шифротекста y1, y2,..., yn восстановить сообщение x1, x2,..., xn, необходимо сгенерировать точно такую же ключевую последовательность k1, yk,..., kn, что и при шифровании, и использовать для расшифрования формулу
Обычно исходное сообщение и ключевая последовательность представляют собой независимые потоки бит. Таким образом, так как шифрующее (и расшифрующее) преобразование для всех поточных шифров одно и то же, они должны различаться только способом построения генераторов ключей. Получается, что безопасность системы полностью зависит от свойств генератора потока ключей. Если генератор потока ключей выдает последовательность, состоящую только из одних нулей (или из одних единиц), то зашифрованное сообщение будет в точности таким же, как и исходный поток битов (в случае единичных ключей зашифрованное сообщение будет инверсией исходного). Если в качестве гаммы используется один символ, представленный, например, восемью битами, то хотя зашифрованное сообщение и будет внешне отличаться от исходного, безопасность системы будет очень низкой. В этом случае при многократном повторении кода ключа по всей длине текста существует опасность его раскрытия статистическим методом. Поясним это на простом примере цифрового текста, закрытого коротким цифровым кодом ключа методом гаммирования.
Пример. Пусть известно, что исходное сообщение представляло собой двоично-десятичное число, то есть число, каждая тетрада (четыре бита) которого получена при переводе десятичной цифры 0...9 в двоичный вид. Перехвачено 24 бита зашифрованного сообщения Y, то есть шесть тетрад Y1, Y2, Y3, Y4, Y5, Y6, а именно значение 1100 1101 1110 1111 0000 0001. Известно, что ключ шифрования состоял из четырех бит, которые тоже представляют собой однозначное десятичное число, то есть одно и то же значение 0≤K≤9 использовалось для шифрования каждых четырех бит исходного сообщения. Таким образом, шифрование числа X1, X2, X3, X4, X5, X6 ключом К можно представить в виде системы уравнений:
Исходя из условия, что Хi принимает десятичные значения от 0 до 9, для поиска неизвестного К определим все возможные значения X1’; и К, сумма которых по модулю 2 приводит к результату 1100:
K = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 Y1 = 1100 1100 1100 1100 1100 1100 1100 1100 1100 1100 --------------------- X1’ = 1100 1101 1110 1111 1000 1001 1010 1011 0100 0101
Так как исходное значение состояло из цифр от 9, то можно исключить из рассмотрения значения ключа 0000, 0001, 0010, 0011, 0110, 0111, так при сложении с ними получаются значения большие 9 в десятичном эквиваленте. Такие значения не могли присутствовать в открытом тексте. Таким образом, первый этап анализа уже позволил сократить количество возможных ключей с десяти до четырех.
Для дальнейшего поиска неизвестного К определим все возможные значения X2’; и оставшихся вариантов ключа, сумма которых по модулю 2 приводит к результату Y2 = 1101:
K = 0100 0101 1000 1001 Y2 = 1101 1101 1101 1101 --------------------- X2’ = 1001 1000 0101 0100
Видно, что этот этап не позволил отбросить ни одного из оставшихся вариантов ключа. Попытаемся это сделать, используя Y3=1110:
K = 0100 0101 1000 1001 Y3 = 1110 1110 1110 1110 --------------------- X2’ = 1010 1011 0110 0111
После проведения этого этапа становится ясно, что ключом не могли быть значения 0100 и 0101. Остается два возможных значения ключа: 1000(2)=8(10) и 1001(2)=9(10).
Дальнейший анализ по данной методике в данном случае, к сожалению, не позволит однозначно указать, какой же из двух полученных вариантов ключа использовался при шифровании. Однако можно считать успехом уже то, что пространство возможных ключей снизилось с десяти до двух. Остается попробовать каждый из двух найденных ключей для дешифровки сообщений и проанализировать смысл полученных вскрытых текстов.
В реальных случаях, когда исходное сообщение составлено не только из одних цифр, но и из других символов, использование статистического анализа позволяет быстро и точно восстановить ключ и исходные сообщения при короткой длине ключа, закрывающего поток секретных данных.
Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от методов математической статистики и имитационного моделирования до криптографии. При этом от качества используемых генераторов псевдослучайных чисел (ГПСЧ) напрямую зависит качество получаемых результатов.
ГПСЧ могут использоваться в качестве генераторов ключей в поточных шифрах. Целью использования
Для использования в криптографических целях
ki использовать и учитывать некоторый секретный ключ, причем вычисление числа ki+1 по известным предыдущим элементам последовательности ki без знания ключа должно быть трудной задачей.При наличии указанных свойств последовательности псевдослучайных чисел могут быть использованы в поточных шифрах.
ki использует формулу
ki=(a*ki-1+b)mod c,
где а, b, с — некоторые константы, a ki-1 — предыдущее псевдослучайное число. Для получения k1 задается начальное значение k0. Возьмем в качестве примера a=5,b=3,c=11 и пусть k0= 1. В этом случае мы сможем по приведенной выше формуле получать значения от 0 до 10 (так как с = 11). Вычислим несколько элементов последовательности:
k1 = (5 * 1 + 3) mod 11 = 8; k2 = (5 * 8 + 3) mod 11 = 10; k3 = (5 * 10 + 3) mod 11 = 9; k4 = (5 * 9 + 3) mod 11 = 4; k5 = (5 * 4 + 3) mod 11 = 1.
Полученные значения (8, 10, 9, 4, 1) выглядят похожими на случайные числа. Однако следующее значение k6 будет снова равно 8:
k6 = (5 * 1 + 3) mod 11 = 8,
а значения k7 и k8 будут равны 10 и 9 соответственно:
k7 = (5 * 8 + 3) mod 11 = 10; k8= (5 * 10 + 3) mod 11 = 9.
Выходит, наш 8, 10, 9, 4, 1. К сожалению, это свойство характерно для всех линейных конгруэнтных генераторов. Изменяя значения основных параметров a, b и c, можно влиять на длину периода и на сами порождаемые значения ki. Так, например, увеличение числа с в общем случае ведет к увеличению периода. Если параметры a, b и c выбраны правильно, то генератор будет порождать случайные числа с максимальным периодом, равным c. При программной реализации значение с обычно устанавливается равным 2b-1 или 2b, где b — длина слова ЭВМ в битах.
Достоинством линейных конгруэнтных k0, k1, k2, k3. Тогда:
k1=(a*k0+b) mod c k2=(a*k1+b) mod c k3=(a*k2+b) mod c
Решив систему из этих трех уравнений, можно найти a, b и c.
Для получения псевдослучайных чисел предлагалось использовать также квадратичные и кубические генераторы:
ki=(a12*ki-1+a2*ki-1+b) mod c ki=(a13*ki-1+a22*ki-1+a3*ki-1+b) mod c
Однако такие генераторы тоже оказались непригодными для целей криптографии по той же самой причине "предсказуемости".
Известны и другие схемы получения псевдослучайных чисел.
Метод Фибоначчи с запаздываниями (Lagged Fibonacci Generator) — один из методов генерации псевдослучайных чисел. Он позволяет получить более высокое "качество" псевдослучайных чисел.
Наибольшую популярность фибоначчиевы датчики получили в связи с тем, что скорость выполнения арифметических операций с вещественными числами сравнялась со скоростью целочисленной арифметики, а фибоначчиевы датчики естественно реализуются в
Известны разные схемы использования метода Фибоначчи с запаздыванием. Один из широко распространённых фибоначчиевых датчиков основан на следующей рекуррентной формуле:
где ki — вещественные числа из диапазона [0,1], a, b — целые положительные числа, параметры генератора. Для работы фибоначчиеву датчику требуется знать max{a,b} предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел необходим некоторый объем памяти, зависящих от параметров a и b.
Пример. Вычислим последовательность из первых десяти чисел, генерируемую методом Фибоначчи с запаздыванием начиная с k5 при следующих исходных данных: a = 4, b = 1, k0=0.1; k1=0.7; k2=0.3; k3=0.9; k4=0.5:
k5 = k1 - k4 = 0.7 - 0.5 = 0.2; k6 = k2 - k5= 0.3 - 0.2 = 0.1; k7 = k3 - k6 = 0.9 - 0.1 = 0.8; k8 = k4 - k7 + 1 =0.5 - 0.8 + 1 = 0.7; k9 = k5- k8 + 1 =0.2 - 0.7 + 1 = 0.5; k10 = k6 - k9 + 1 =0.1 - 0.5 + 1 = 0.6; k11 = k7 - k10 = 0.8 - 0.6 = 0.2; k12 = k8 - k11 = 0.7 - 0.2 = 0.5; k13 = k9 - k12 + 1 =0.5 - 0.5 + 1 = 1; k14 = k10 - k13 + 1 =0.6 - 1 + 1 = 0.6.
Видим, что генерируемая последовательность чисел внешне похожа на случайную. И действительно, исследования подтверждают, что получаемые случайные числа обладают хорошими статистическими свойствами.
Для генераторов, построенных по (a,b) = (55, 24), (17, 5) или (97,33). Качество получаемых случайных чисел зависит от значения константы a: чем оно больше, тем выше размерность пространства, в котором сохраняется равномерность случайных векторов, образованных из полученных случайных чисел. В то же время с увеличением величины константы a увеличивается объём используемой алгоритмом памяти.
В результате значения (a,b) = (17,5) рекомендуются для простых приложений. Значения (a,b) = (55,24) позволяют получать числа, удовлетворительные для большинства криптографических алгоритмов, требовательных к качеству случайных чисел. Значения (a,b) = (97,33) позволяют получать очень качественные случайные числа и используются в алгоритмах, работающих со случайными векторами высокой размерности.
Генераторы ПСЧ, основанные на методе Фибоначчи с запаздыванием, использовались для целей криптографии. Кроме того, они применяются в математических и статистических расчетах, а также при моделировании случайных процессов. Генератор ПСЧ, построенный на основе метода Фибоначчи с запаздыванием, использовался в широко известной системе Matlab.
Широкое распространение получил алгоритм генерации псевдослучайных чисел, называемый алгоритмом BBS (от фамилий авторов — L. Blum, M. Blum, M. Shub) или генератором с квадратичным остатком. Для целей криптографии этот метод предложен в 1986 году.
Он заключается в следующем. Вначале выбираются два больших p и q. Числа p и q должны быть оба сравнимы с 3 по модулю 4, то есть при делении p и q на 4 должен получаться одинаковый остаток 3. Далее вычисляется число M = p* q, называемое целым числом Блюма. Затем выбирается другое случайное целое число х, взаимно простое (то есть не имеющее общих делителей, кроме единицы) с М. Вычисляем х0= х2mod M. х0 называется стартовым числом генератора.
На каждом n-м шаге работы генератора вычисляется хn+1= хn2 mod M. Результатом n-го шага является один (обычно младший) бит числа хn+1. Иногда в качестве результата принимают бит чётности, то есть количество единиц в двоичном представлении элемента. Если количество единиц в записи числа четное – бит четности принимается равным 0, нечетное – бит четности принимается равным 1.
Например, пусть p = 11, q = 19 (убеждаемся, что 11 mod 4 = 3, 19 mod 4 = 3). Тогда M = p* q = 11*19=209. Выберем х, взаимно простое с М: пусть х = 3. Вычислим стартовое число генератора х0:
х0 = х2 mod M = 32 mod 209 = 9 mod 209 = 9.
Вычислим первые десять чисел хi по алгоритму хi:
х1=92 mod 209= 81 mod 209= 81 | младший бит: | 1 |
х2=812 mod 209= 6561 mod 209= 82 | младший бит: | 0 |
х3=822 mod 209= 6724 mod 209= 36 | младший бит: | 0 |
х4=362 mod 209= 1296 mod 209= 42 | младший бит: | 0 |
х5=422 mod 209= 1764 mod 209= 92 | младший бит: | 0 |
х6=922 mod 209= 8464 mod 209= 104 | младший бит: | 0 |
х7=1042 mod 209= 10816 mod 209= 157 | младший бит: | 1 |
х8=1572 mod 209= 24649 mod 209= 196 | младший бит: | 0 |
х9=1962 mod 209= 38416 mod 209= 169 | младший бит: | 1 |
х10=1692 mod 209= 28561 mod 209= 137 | младший бит: | 1 |
Самым интересным для практических целей свойством этого метода является то, что для получения n-го числа последовательности не нужно вычислять все предыдущие n чисел хi. Оказывается хn можно сразу получить по формуле
Например, вычислим х10 сразу из х0:
В результате действительно получили такое же значение, как и при последовательном вычислении, – 137. Вычисления кажутся достаточно сложными, однако на самом деле их легко оформить в виде небольшой процедуры или программы и использовать при необходимости.
Возможность "прямого" получения хn позволяет использовать алгоритм
Безопасность алгоритма М на множители. Утверждается, что если М достаточно велико, его можно даже не держать в секрете; до тех пор, пока М не разложено на множители, никто не сможет предсказать выход генератора ПСЧ. Это связано с тем, что задача разложения чисел вида n = pq (р и q — простые числа) на множители является вычислительно очень трудной, если мы знаем только n, а р и q — большие числа, состоящие из нескольких десятков или сотен бит (это так называемая задача факторизации).
Кроме того, можно доказать, что злоумышленник, зная некоторую последовательность, сгенерированную генератором М на множители.
Самым существенным недостатком алгоритма является то, что он недостаточно быстр, что не позволяет использовать его во многих областях, например, при вычислениях в реальном времени, а также, к сожалению, и при
Зато этот алгоритм выдает действительно хорошую последовательность псевдослучайных чисел с большим периодом (при соответствующем выборе исходных параметров), что позволяет использовать его для криптографических целей при генерации ключей для шифрования.
Stream cipher –
Алгоритм BBS – один из методов генерации псевдослучайных чисел. Название алгоритма происходит от фамилий авторов - L. Blum, M. Blum, M. Shub. Алгоритм может использоваться в криптографии. Для вычислений очередного числа M = pq является произведением двух больших простых p и q.
Генератор псевдослучайных чисел (ГПСЧ) – некоторый алгоритм или устройство, которые создают последовательность битов, внешне похожую на случайную.
Линейный конгруэнтный генератор псевдослучайных чисел – один из простейших ГПСЧ, который для вычисления очередного числа ki использует формулу ki=(a*ki-1+b)mod c, где а, b, с — некоторые константы, a ki-1 — предыдущее псевдослучайное число.
Метод Фибоначчи с запаздываниями – один из методов генерации псевдослучайных чисел. Может использоваться в криптографии.
Поточный шифр – шифр, который выполняет шифрование входного сообщения по одному биту (или байту) за операцию. Поточный алгоритм шифрования устраняет необходимость разбивать сообщение на целое число блоков.
В качестве генераторов ключей в поточных шифрах могут использоваться
Простейшими генераторами псевдослучайных чисел являются: линейный конгруэнтный генератор, генератор по
а, b и c (k0 принять равным 0):
а =5, b =7 и c = 17;а = 6, b =3 и c = 23.kа при следующих исходных данных:
a = 3, b = 1, k0=0.6; k1=0.3; k2=0.5;a = 4, b = 2, k0=0.9; k1=0.3; k2=0.5; k3=0.9.k0, k1, k2, k3, полученные с помощью линейного конгруэнтного генератора, равны: k0 = 1, k1 = 12, k2 = 3, k3 = 6. Найдите параметры а, b и c генератора ПСЧ.х11 по методу генерации псевдослучайных чисел p = 11, q = 19, х = 3.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.