Конспект лекций для студентов, магистров и аспирантов всех специальностей

Вид материала

Конспект

Содержание Понятие функции с секретом (функции с ловушкой). Криптосистема открытого шифрования RSA (R.L.Rivest, A. Shamir, L. Adleman, 1978) Пример на использование системы RSA Понятие хеш функции Организация электронной подписи в криптосистеме RSA. Электронные деньги. Неотслеживаемость. Пример простейшего криптографического протокола. Деловая задача. Список литературы Защита информации от случайных помех. Код Р. Хэмминга.

Подобный материал:

• Конспект лекций бурлачков в. К., д э. н., проф. Москва, 1213.67kb.
• Конспект лекций для студентов всех специальностей дневной и заочной формы обучения, 1439.07kb.
• Курс лекций (для магистров всех специальностей Академии) харьков − 2006, 1136.42kb.
• Конспект лекций по курсу основы алгоритмизации и программирования для студентов всех, 3059.86kb.
• Конспект лекций по курсу Начертательная геометрия (для студентов заочной формы обучения, 1032.28kb.
• Конспект лекций для студентов по специальности i-25 01 08 «Бухгалтерский учет, анализ, 2183.7kb.
• Конспект лекций по курсу "Начертательная геометрия и инженерная графика" Кемерово 2002, 786.75kb.
• Конспект лекций по дисциплине «Маркетинг», 487.79kb.
• Конспект лекций для студентов специальности 080110 «Экономика и бухгалтерский учет, 1420.65kb.
• Конспект лекций по культурологии Для студентов всех специальностей, 4611.53kb.

^

Понятие функции с секретом (функции с ловушкой).

Функцией с секретом называется функция f _K : X Y, зависящая от параметра K и обладающая тремя свойствами:

1. существует полиномиальный алгоритм вычисления значения
   

f _K (x) для любых K и x.

2. не существует полиномиального алгоритма инвертирования f _K при неизвестном K.
   
3. существует полиномиальный алгоритм инвертирования f _K при известном K.
   

Функции с ловушкой применяются в криптосистеме открытого шифрования RSA.


^ Криптосистема открытого шифрования RSA (R.L.Rivest, A. Shamir, L. Adleman, 1978)


Абоненты A и B независимо друг от друга выбирают два достаточно больших простых числа

p _i и q _i (i=A, B)

и вычисляют их произведения

N _i = p _i q _i

и числа

F _i = (p _i – 1) (q _i – 1).

Далее каждый из них выбирает по достаточно большому числу e _i , взаимно простому с числом F _i так, чтобы имело место равенство

e _i d _i = 1 (mod F _i )

Итак, Абоненты A и B имеют свои наборы чисел

p _i , q _i , N _i , F _i , e _i , d _i (i= A, B)

и готовы к обмену конфиденциальной информацией.

Далее они помещают числа

N _i , e _i (i=A, B)

на открытом сервере, а числа

p _i , q _i , F _i

обычно уничтожают, так как в дальнейшем они не понадобятся. Числа же

d _i

каждый из них хранит у себя в качестве секретного ключа расшифрования.

В качестве односторонней функции с секретом в системе RSA используется функция:


e _i

y= f(x)=x (mod N _i)

Действие системы основано на равенстве, вытекающем из теоремы Эйлера и малой теоремы Ферма

d _i

x = f ^-1 (y) = y (mod N _i )


На доказательстве этой формулы не останавливаемся.

^

Пример на использование системы RSA

Для иллюстрации своего метода Ривест, Шамир и Адлеман записали английскую фразу:


The magic words are squeamish ossifrage.


Сначала они стандартным образом (a=01, b=02, …, z=26, пробел=00) записали её в виде целого числа


x= 2008050013010709030023151804190001180500191721051309190

800151919090618010705 (76 цифр),


а затем зашифровали при помощи отображения

e

y= f(x)=x (mod N )


при


e=9007

и

N=1438162575788886766932577997614661200218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541 (127 цифр).


В результате получили зашифрованный текст:


f(x)=96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154 (128 цифр).


Текст f(x) и числа N, e были опубликованы, причём дополнительно сообщалось, что N=pq, где p и q – простые числа, записываемые соответственно 64 и 65 десятичными знаками. Тому, кто дешифрует сообщение F(x) была обещана награда в $100.

Эта история завершилась спустя 17 лет в 1994 г., когда D. Atkins, M. Graff, A.K. Lenstra и P.S. Leyand сообщили о дешифровании фразы f(x).

Числа p и q при этом оказались равными

p=3490529510847650949147849619903898133417764638493387843990820577 (64 цифры)


q=32769132993266709549961988190834461413177642967992942539798288533 (65 цифр)


В работе, возглавлявшейся четырьмя названными авторами проекта, после теоретической подготовки на заключительном этапе длительностью в 220 дней принимали участие около 600 человек и примерно 1600 компьютеров, объединённых сетью Internet. Премия в $100 была передана в Free Sofware Foundation.

Лекция 7

^ Понятие хеш функции


(hash – случайные данные). x – передаваемое сообщение (текст). h(x) – функция аргумента x, обладющая следующими свойствами:

1) Хеш функция должна быть чувствительной ко всевозможным изменениям аргумента x.

2) Хеш функция должна обладать свойством необратимости, т.е. задача подбора текста при заданном значении функции должна быть вычислительно неразрешимой.

3) Вероятность того, что значения h(x) для двух различных текстов совпадут должна быть ничтожно малой.

Выбор такой функции всегда можно осуществить при помощи односторонних функций.


^ Организация электронной подписи в криптосистеме RSA.

1. Абонент A вычисляет хеш функцию h(x) от аргумента x передаваемого сообщения.
   

2) Шифрует сообщение x открытым ключом абонента B:

e_B

f(x)=x (mod N_B )

либо не шифрует, если в шифровании текста сообщения нет необходимости.

2. Ставит свою подпись под h(x), т.е. вычисляет число
   

d _A

S(h(x))=(h(x)) (mod N_A ),

другими словами, шифрует хеш функцию своим закрытым ключом

d _A . Текст f(x), (либо x) с подписью S(h(x)) отправляется абоненту B по открытому каналу связи.

Абонент B расшифровывает текст своим секретным ключом:

d_B

x= (f(x)) (mod N_B ),

либо не расшифровывает, если он не был зашифрован. Затем абонент B вычисляет хеш функцию h* (x) от текста x и сверяет её с результатом расшифрования подписи открытым ключом абонента A, т.е. проверяет справедливость равенства

e _A

h*(x)=S(h(x)) (mod N_A ).


Если значение хеш функции текста совпадёт со значением хеш функции, полученной в результате расшифрования подписи абонента A, то подпись принимается, и отвергается в противном случае.

Если противник узнает число S, то он сможет восстановить хеш функцию h для данного текста абонента A, так как открытый ключ абонента A общедоступен. Однако, он не сможет имитировать посылку текстов абоненту B от имени, якобы абонента A, так как для этого нужно знать секретный ключ абонента A.

От подписи нельзя отказаться, потому что открытому ключу соответствует закрытый ключ, принадлежащий тому, кто ставил подпись.

Итак, абонент B, имея текст x, его хеш функцию h(x) и число S(h(x)), имеет убедительный аргумент в пользу того, что он получил текст именно от абонента A.


^ Электронные деньги. Неотслеживаемость.


Столь популярная ныне во всём мире кредитная карточка представляет собой носитель информации, который при каждом платеже полностью идентифицирует своего владельца. И если владелец использует её для покупки билетов на транспорт , то можно отследить все его поездки, что в цивилизованном обществе без санкции прокурора недопустимо. Аналогичным образом, для каждого владельца кредитных карточек возможно собирать информацию о том, какие товары и где он покупает, какими услугами пользуется, какие культурно-зрелищные мероприятия посещает и т. д.

Дальше — больше. Организация компьютерного доступа к информации и перевод документов в электронную форму создадут предпосылки для ведения досье, отражающих весь круг интересов каждого из граждан. Этот перечень угроз правам и свободам личности, безусловно, можно продолжить. Резюмируя, можно сказать, что компьютеризация создаёт беспрецедентные возможности для организации тотальной слежки. Угроза эта тем более серьёзная, что она до сих пор ещё не осознана даже многими специалистами.

Для предотвращения подобной угрозы необходима система контроля за доступом к ресурсам, которая удовлетворяет двум, казалось бы, взаимно исключающим требованиям. Во-первых, всякий желающий должен иметь возможность обратиться к этой системе анонимно, а во-вторых, при этом всё же доказать своё право на доступ к тому или иному ресурсу. Обычные бумажные деньги обеспечивают оба этих свойства. Если ресурсом, например, является некоторый товар, то наличие у покупателя достаточного количества купюр является доказательством его права на доступ к ресурсу. С другой стороны, хотя каждая бумажная купюра и имеет уникальный номер, отслеживать купюры по номерам практически невозможно. Кредитные карточки удовлетворяют только второму требованию.

Всюду ниже под электронными деньгами мы будем понимать электронные платёжные средства, обеспечивающие неотслеживаемость. Понятие неотслеживаемости, по-видимому, не может быть формализовано и будет поясняться на конкретных примере протокола.

Для работы с электронными деньгами разрабатываются специальные криптографические протоколы, называемые протоколами электронных платежей. В таком протоколе задействованы три участника, которых мы будем называть: банк, покупатель и продавец. Покупатель и продавец, каждый, имеют счёт в банке, и покупатель желает заплатить продавцу за товар или услугу. В платёжной системе используются три основные транзакции:

-снятие со счёта;

-платёж;

-депозит.

В транзакции снятия со счёта покупатель получает подписанную банком электронную банкноту на затребованную сумму. При этом счёт покупателя уменьшается на эту сумму. В транзакции платежа покупатель передаёт банкноту продавцу и указывает сумму платежа. Продавец, в свою очередь, передаёт эту информацию банку, который проверяет подлинность банкноты. Если банкнота подлинная, банк проверяет, не была ли она потрачена ранее. Если нет, то банк заносит банкноту в специальный регистр, зачисляет требуемую сумму на счёт продавца, уведомляет продавца об этом, и, если достоинство банкноты выше, чем сумма платежа, возвращает покупателю сдачу (через продавца). С помощью транзакции депозита, покупатель может положить сдачу на свой счёт в банке.

Безопасность банка основывается на невозможности подделать его подпись для создания фальшивой банкноты, или, более общим образом, на невозможности, получив набор подлинных электронных банкнот, подделать подпись ещё хотя бы для одной банкноты. Для неотслеживаемости покупателя необходимо, чтобы банк, получив банкноту в транзакции платежа, не мог установить, кому она была выдана. То же относится и к сдаче. Это, казалось бы, парадоксальное требование удовлетворяется с помощью схемы так называемой затемнённой (слепой) подписи: в транзакции снятия со счёта банк подписывает не банкноту, а некоторую абракадабру, из которой покупатель восстанавливает подлинную банкноту. Таким образом, неотслеживаемость гарантируется тем, что банк просто не знает, что именно он подписал.


^ Пример простейшего криптографического протокола.

Рассмотрим простейший вариант платёжной системы, в которой используется затемнённая подпись, соответствующая схеме подписи RSA. Последняя основана на тех же принципах, что и криптосистема RSA. Подписывающий, в нашем случае — банк, выбирает два секретных простых числа p и q достаточно большой длины и публикует их произведение N=pq. Пусть e и d , где ed=1 (mod φ(N)), - соответственно открытый и секретный ключи криптосистемы RSA. Генерация подписи в схеме электронной подписи RSA состоит в применению к сообщению m функции дешифрования криптосистемы RSA:

d

s=m (mod N).

Для проверки подписи нужно применить к ней функцию шифрования. Если

e

s =m (mod N),

то s — корректная подпись для сообщения m.

Итак, банк выбирает и публикует числа N и e, а также некоторую одностороннюю функцию f: Z_N→Z_N , назначение которой станет ясно из дальнейшего. Пара ключей (e, d) используется банком исключительно для создания электронных банкнот, т.е. устанавливается соглашение о том, что электронной подписи, сгенерированной на ключе d, соответствует электронная банкнота достоинством, скажем, скажем, в один фантик.

В транзакции снятия со счёта покупатель выбирает случайное число n  Z_N и вычисляет f(n). Ему нужно получить подпись банка на этой банкноте, т.е. значение


d

f(n) . Но просто послать значение f(n) покупатель банку покупатель не может, поскольку для снятия денег со счёта он должен идентифицировать себя. Поэтому, если банк получает f(n), он в дальнейшем всегда узнает данную банкноту и неотслеживаемость будет потеряна. Решение проблемы состоит в использовании затемнённой подписи: покупатель выбирает случайное число

r  Z_N, r 0, вычисляет


e e

f(n)r ( mod N) и посылает это значение банку. Множитель r часто называют затемняющим множителем. Банк вычисляет значение

d

f(n) r (mod N) и возвращает его покупателю. Покупатель легко снимает затемняющий множитель r и получает подписанную банкноту

d

(n, f(n) mod N).

В транзакции платежа покупатель передаёт продавцу электронную банкноту

d

(n, f(n) mod N). В принципе, продавец может проверить подлинность любой банкноты (n, s) самостоятельно. Для этого достаточно вычислить f(n) и проверить, что

e

f(n)=s (mod N). Но дело в том, что электронные банкноты, как и любую другую информацию, представленную в электронной форме, легко копировать. Поэтому нечестный покупатель может заплатить одной и той же электронной банкнотой многократно. Для предотвращения подобного злоупотребления продавец передаёт банкноту на проверку банку. Банк проверяет по специальному регистру, не была ли эта банкнота потрачена ранее, и если нет, то зачисляет один фантик на счёт продавца и уведомляет его об этом.

Безопасность банка в этой системе электронных платежей основывается на вере в стойкость схемы электронной подписи RSA. Применение функции f в этой конструкции необходимо ввиду известного свойства мультипликативности схемы RSA: если s₁ и s₂

• подписи для m₁ и m₂ соответственно, то
  

d d

s₁  s₂=m₁  m₂ (mod N) - подпись для m₁  m₂. Поэтому, если бы в системе электронных платежей использовались банкноты вида

d

(n, n mod N), то из двух подлинных банкнот всегда можно было бы изготовить третью. Неотслеживаемость клиентов в данной системе абсолютна. Всё, что остаётся у банка от транзакции снятия со счёта, - это значение

d

f(n)  r (mod N), которое благодаря затемняющему множителю r представляет собой просто случайное число из Z_N. Поэтому у банка нет никакой информации о том, какую именно банкноту он выдал данному клиенту.

В этом примере банк выдаёт купюры только достоинством в один фантик и все платежи должны быть кратны этой величине. Здесь мы отметим только, что существуют более гибкие схемы электронных платежей с банкнотами разного достоинства, выдачей сдачи и т. п., но эти схемы мы не рассматриваем.

^ Деловая задача.


Можно ли определить фамилии должностных лиц банка, если известно, что


Штат состоит из 11 служащих: президент, первый вице-президент, второй вице-президент, третий вице- президент, главный бухгалтер, кассир, контролёр, счетовод, первый секретарь президента банка, второй секретарь (оба секретаря владеют стенографией) и швейцар. Известны фамилии этих одиннадцати сотрудников банка: мистер Адамс, миссис Браун, мистер Грант, мисс Дейл, мистер Джоунс, миссис Кейн, мистер Кемп, мистер Лонг, миссис Форд, мисс Хилл и мистер Эванс. Относительно служащих банка известно следующее.

1. Президент банка души не чает в своём внуке, исполняющем обязанности третьего вице-президента, миссис Браун и контролёр банка недолюбливают последнего.
   

2. Контролёр и второй секретарь потеряли недавно своего отца и супруга.
   

3. Второй вице-президент банка и контролёр носят шляпы одинакового фасона.
   

4. Мистеру Гранту понадобилось продиктовать деловое письмо, и он потребовал, чтобы мисс Хилл срочно прислала ему секретаря.
   

5. Миссис Кейн, мистер Грант и мистер Лонг – соседи президента банка; все остальные сотрудники живут довольно далеко.
   

6. Первый вице-президент и главный бухгалтер живут в фешенебельном “Клубе холостяков”.
   

7. Швейцар красит бороду и никого не приглашает в свою комнатку под самой крышей.
   

8. Банковские служащие молодого поколения, ещё не успевшие обзавестись собственными семьями, регулярно собираются у одного из своих коллег, чаще всего у мистера Адамса и второго секретаря.
   

9. Второй вице-президент банка и счетовод некогда были помолвлены.
   

10. Неизменно одетый по последней моде кассир доводится зятем первому секретарю президента банка.
    

11. Мистер Джоунс в тайне от счетовода, который среди служащих является старшим по возрасту, регулярно отдаёт свои поношенные платья мистеру Эвансу.
    

Ответ: Можно.

Президент миссис Форд

Первый вице-президент мистер Грант

Второй вице-президент мисс Хилл

Третий вице- президент мистер Адамс

Главный бухгалтер мистер Лонг

Кассир мистер Джоунс

Контролёр миссис Кейн

Счетовод мистер Кемп

Первый секретарь президента банка миссис Браун

Второй секретарь мисс Дейл

Швейцар мистер Эванс


Решение:


Непосредственно из условий задачи следует, что следующие пять должностей в банке занимают мужчины: должность первого вице-президента по (условию 6),

третьего вице-президента (по условию 1),

главного бухгалтера (по условию 6),

кассира (по условию 10) и

швейцара (по условию 7).

По условию 3 второй вице-президент и контролёр - лица одного пола, а поскольку среди служащих имеется только шесть мужчин, то обязанности второго вице-президента и контролёра в банке исполняют женщины. Поскольку второй вице-президент банка - женщина, то по условию 9 счетовод - мужчина. Таким образом, обязанности президента и второго вице-президента банка, контролёра, а также первого и второго секретарей президента банка исполняют женщины. Поскольку президент банка имеет внука и потому не может быть мисс и поскольку это не миссис Браун (по условию 1) , а также не миссис Кейн (по условию 5), то пост

президента банка занимает миссис Форд. Мисс Хилл не секретарь (по условию 4), и второй секретарь не состоит в браке (по условию 8), следовательно, обязанности второго секретаря исполняет мисс Дейл. По условию 2 контролёр является её матерью, следовательно,

контролёр - миссис, а поскольку обязанности контролёра исполняет не миссис Браун (по условию 1), то этот пост может занимать только миссис Кейн. Первый секретарь президента банка - замужняя женщина (по условию 10). Следовательно, это миссис Браун.

Таким образом, обязанности второго вице-президента исполняет мисс Хилл. По условию 4 мистер Грант может отдавать распоряжения мисс Хилл. Следовательно, он занимает более высокий пост в банке. Поскольку президент банка - женщина, то мистер Грант может быть только первым вице-президентом банка. По условию 6 мистер Грант живёт в "Клубе холостяков" вместе с главным бухгалтером. Следовательно (по условию 5), пост главного бухгалтера может занимать только мистер Лонг. Представитель молодого поколения служащих банка мистер Адамс (условие 8) не может исполнять обязанности счетовода, который (по условию 11) принадлежит к старшему поколению служащих. Из того же условия

11 следует, что ни мистер Джоунс, ни мистер Эванс не могут быть счетоводами. Таким образом, на посту счетовода трудится мистер Кемп. Не успевший обзавестись собственной семьёй (условие 8) мистер Адамс, принимающий у себя молодых служащих банка,

не может быть ни женатым кассиром из условия 10, ни живущим в комнатке под самой крышей швейцаром из условия 7. Следовательно, мистер Адамс третий вице-президент банка.

Следящий за модой кассир (условие 10) не стал бы принимать поношенное платье. Поэтому обязанности кассира исполняет не мистер Эванс (условие 11), им может быть только мистер Джоунс. Наконец, мистер Эванс из условия 11 должен быть швейцаром.

Состояние его гардероба вполне согласуется с его скромным жилищем (условие 7).


^

Список литературы

1. Алфёров А.П., Зубов А.Ю., Кузьмин А.С. Основы
   

криптографии, М.: Гелиос-АРВ, 3-е издание , 2005 г., 480 с.

2. Михаэль А. Бэнкс. Информационная защита ПК. Перев. с англ. Киев “ВЕК+”, Москва “Энтроп”, Санкт-Петербург “Корона-Принт”, 2001, 272 с.
   

3. Новые математические дисциплины. Введение в криптографию. Под общей редакцией В.В.Ященко. МЦНМО – ЧеРо, М.: 2000, 288 с.
   

4. Анохин М.И., Варновский Н.П., Сидельников В.М., Ященко В.В. Криптография в банковском деле. Москва, МИФИ, 1997
   

5. Аветисян Р.Д., Аветисян Д.О. Теоретические основы

1. информатики. Москва, РГУ, 1997, 168 с.
   

2. 6. Виноградов И.М. Основы теории чисел. М.: Наука, 1972, 168 с.
   

Содержание.


Лекция 1.

Введение. P, V, S протоколы. Уровни защищаемой информации. Технические аспекты защиты информации. Схема обмена конфиденциальной информацией в открытой сети. Кодирование информации.

Лекция 2.

Принципы архивирования (сжатия) информации. Схема двоичного кодирования по Р. Фано (R.Fano). Схема двоичного кодирования текстов по Д. А. Хаффмэну (1952).

Лекция 3.

Сведения из теории информации по К. Шеннону (Shannon C.E., 1945). Необходимые сведения из арифметики.

Лекция 4.
^

Защита информации от случайных помех. Код Р. Хэмминга.

Из истории криптографии. Математические основы шифрования. Шифр замены. Шифр перестановки.

Лекция 5.

Существование и единственность абсолютно стойкого шифра.

Понятие полиномиального алгоритма. Понятие односторонней функции. Односторонняя функция Диффи и Хеллмана.

Протокол выработки общего ключа удалёнными абонентами.

Лекция 6.

Понятие функции с секретом (функции с ловушкой).

Криптосистема открытого шифрования RSA (R.L.Rivest, A. Shamir, L. Adleman, 1978). Пример на использование системы RSA

Лекция 7.

Понятие хеш функции. Организация электронной подписи в криптосистеме RSA. Электронные деньги. Неотслеживаемость.

Деловая задача.

Список литературы.