Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Криптографические протоколы.

1. Дайте определение единице количества вещества - молю.

2. Что называется числом Авогадро?

3. Что называется молярной массой?

4. Что называется давлением? Какова единица измерения давления в СИ?

5. Какой газ называется идеальным?

6. Записать и объяснить основное уравнение молекулярно-кинетической
теории идеального газа.

7. Записать формулу средней кинетической энергии поступательного движения молекулы.

8. Каков молекулярно-кинетический смысл температуры?

9. Каково соотношение между температурами по шкале Цельсия и абсолютной температурой (по шкале Кельвина)?

10. Какой физический смысл функции распределения молекул идеального газа по скоростям (распределение Максвелла)? Нарисовать графики этой функции при разных температурах.

11. Что называется средней квадратичной, средней арифметической и наиболее вероятной скоростями молекул, написать формулы.

12. Записать закон Больцмана для распределения молекул во внешнем силовом поле.

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

14. Какими параметрами характеризуется состояние идеального газа?

15. Записать и объяснить уравнение состояния идеального газа (уравнение Менделеева-Клапейрона).

16. Какие процессы называются изотермическими, изобарическими и изохорическими? Вывести их уравнения из уравнения состояния идеального газа. Нарисовать их графики в координатах (р, V), (р,Т) и (V,T).

17. Какой смысл имеет выражение "число степеней свободы молекулы"? Чему равно число степеней свободы молекул одноатомных, двухатомных и многоатомных молекул газов?

18. Как распределяется энергия молекулы по степеням свободы? Запишите формулу полной кинетической энергии молекулы.

19. Что такое внутренняя энергия газа? Запишите формулу внутренней энергии некоторой массы идеального газа.

20. Записать формулу работы расширения газа при различных изопроцессах.

21. Сформулируйте первое начало термодинамики. Каким уравнением оно выражается? Какой вид принимает это уравнение для различных изопроцессов?

22. Что такое удельная и молярная теплоемкости вещества? Каково соотношение между ними?

23. Записать формулы молярных теплоемкостей идеального газа при изобарическом процессе (С_р) и изохорическом процессе (C_V).

24. Какой процесс называется адиабатическим? Записать уравнение адиабатического процесса (уравнение Пуассона) и первое начало термодинамики при этом процессе.

25. Что происходит с температурой при адиабатическом расширении газа и при адиабатическом сжатии?

26. В чем заключаются явления переноса: диффузия, теплопроводность и вязкость. Запишите их уравнения. Каков физический смысл коэффициентов диффузии, теплопроводности и вязкости?

27. Что такое тепловая машина? Чему равен ее коэффициент полезного действия (КПД)?

28. Из каких процессов состоит цикл Карно? Изобразить график цикла Карно

в координатах (р, V). Записать формулу КПД цикла Карно.

29. Сформулировать второе начало термодинамики.

30. Какие процессы называются обратимыми и какие необратимыми?

31. Какой физический смысл энтропии? Чему равно изменение энтропии при обратимом и необратимом процессах?

32. Сформулировать второе начало термодинамики через понятие энтропии.

33. Записать и объяснить уравнение состояния реального газа (уравнение Ван-дер-Ваальса).

34. Нарисовать изотермы Ван-дер-Ваальса и экспериментально полученные изотермы реальных газов.

35. Какое состояние вещества называется критическим?

Криптографические протоколы.

Основные понятия модулярной арифметики

Множество всех целых чисел с операциями сложения и умножения называют кольцом целых чисел.

Для любого целого a > 0 справедливо равенство a= k∙n+r_a, где k – целое число – частное от деления a на натуральное число n, r_a остаток от деления a на n. Величина r_a может принимать значения лишь из множества Z/n={0,1,2,..,,(n –1)}. Равенство a=k∙n+r_a записывают в новом виде a º r_a, mod n и читают так: «a сравнимо с r_a по модулю n». На множестве Z/n вводят операции сложения по модулю n, умножения по модулю n. Результатом сложения по модулю n чисел a,b является остаток r_a+b от деления (a + b) на n. Это записывают в виде (a + b) = r_a+b mod n. Аналогично вводится операция умножения по модулю n: (a∙b) = r_a∙b mod n. Напоминаем, что операции проводятся над возможными остатками - вычетами {0,1,2,..,,(n –1)} от деления на n целых неотрицательных чисел. Например, для n=12 полный набор вычетов: Z/12={0,1,2,…,11}, 2+5=7 mod12, 9+4=1 mod12, 11+11=10 mod12, 2+0=2 mod12 2∙5=10 mod12, 9∙4=0 mod12, 11∙11=1 mod12. Здесь и ниже индексы у остатков опускаются. Множество Z/n={0,1,2,..,,(n –1)} с введенными операциями сложения и умножения по модулю n называют кольцом целых по модулю n (кольцом вычетов по модулю n).

Получение остатка a mod n от деления на n произвольного целого числа a называют приведением по модулю n. Эта операция обладает хорошим свойством называемым гомоморфизмом: мы можем либо сначала приводить числа по модулю n, а затем выполнять операции сложение, умножение, либо сначала выполнять операции, а затем приводить полученное число по модулю n. Более точно: приведение по модулю n является гомоморфным отображением кольца целых чисел в кольцо целых по модулю n. Легко проверяется, что

(a + b) mod n = [a (mod n) + b (mod n)] mod n,

(a – b) mod n = [a (mod n) – b (mod n)] mod n,

(a ∙ b) mod n = [a (mod n) ∙ b (mod n)] mod n,

[a ∙ (b + c)] mod n = {[a∙ b (mod n)] + [a∙ c (mod n)]} mod n.

Вычисление a^x mod n - степени числа a по модулю n как следует из записи можно выполнить как ряд умножений и последним действием выполнить деление получая остаток. Можно вычислить эту степень быстрее, производя возведение в степень как ряд последовательных умножений совместно с приведением по модулю. Это особенно заметно, если работать с большими числами (в битах 200 бит и более). Например, если нужно вычислить a⁸ mod n, то выполняют три малых умножения и три малых приведения по модулю:

((a² mod n)² mod n)² mod n.

Тем же способом вычисляют

a¹⁶ mod n = (((a² mod n)² mod n)² mod n)² mod n.

Вычисление a^x mod n, где x не является степенью 2, лишь немного сложнее. Двоичная запись числа x позволяет представить число x как сумму степеней 2: x = 25₍₁₀₎ ® 1 1 0 0 1₍₂₎ – двоичное представление числа 25, поэтому 25 = 2⁴ + 2³ + 2⁰. Тогда

a²⁵ mod n = (a∙a²⁴) mod n = (a∙a⁸∙a¹⁶) mod n =

= a ∙ ((a²)²)² ∙ (((a²)²)²)² mod n = ((((a^{2 ∙} a)²)²)² ∙ a) mod n.

Алгоритм Евклида для нахождения наибольшего общего делителя. Целое число a делит без остатка другое целое число b, если, и только если

b = k ∙ a

для некоторого целого числа k (т.е. остаток отделения равен 0). В этом случае a называют делителем числа b или множителем в разложении числа b на множители.

Пусть a – целое число, большее 1. Тогда a является простым числом, если его единственными положительными делителями будут 1 и само a, в противном случае a называется составным. Любое целое n >1 может быть представлено единственным образом с точностью до порядка сомножителей как произведение простых.

Существенный с точки зрения криптографии факт состоит в том, что не известно никакого эффективного алгоритма разложения чисел на множители. Более точно. Криптографическая стойкость ряда шифров с открытым ключом держится именно на отсутствии эффективного алгоритма разложения чисел на множители.

Наибольший общий делитель чисел a и b, обозначаемый как НОД (a,b) или просто (a,b), – это наибольшее целое, делящее одновременно числа a и b. В эквивалентной форме (a,b) – это то, единственное натуральное число, которое делит a и b и делится на любое целое, делящее и a и b. Если НОД (a,b)=1, то целые a и b – взаимно простые.

Наибольший общий делитель может быть вычислен с помощью алгоритма Евклида. Опишем алгоритм Евклида для нахождения НОД(a,b). Введем обозначения: q_i – частное; r_i – остаток. Тогда алгоритм можно представить в виде следующей цепочки равенств:

a = b ∙q₁ + r₁, 0 < r₁< b,

b = r₁ ∙ q₂ + r₂, 0 < r₂< r₁,

r₁ = r₂ ∙ q₃ + r₃, 0 < r₃< r₂,

M M

r_k–2 = r_k–1 ∙ q_k + r_k, 0 < r_k< r_k–1,

r_k–1 = r_k ∙ q_k+1.

Остановка гарантируется, поскольку остатки r_i от делений образуют строго убывающую последовательность натуральных чисел. Из этой цепочки немедленно получаем, что r_k есть общий делитель чисел a и b и, более того, что любой общий делитель чисел a и b делит и r_k. Таким образом, r_k = НОД(a, b) или r_k = (a, b).

Отметим, что при операции умножения действительных чисел нетрудно вычислить мультипликативную обратную величину a^–1 для ненулевого числа a: a^–1 =1/a или a ∙ a^–1 =1. Например, мультипликативная обратная величина от числа 4 равна 1/4, поскольку 4 =1.

Обращаем особое внимание, что при операции умножения по модулю n в кольце Z/n={0,1,2,..,(n –1)} вычисление обратной величины для , т.е. величины x, для которой a∙x mod n =1 является более сложной задачей. Например, решение сравнения 4∙x º1 (mod 7) эквивалентно нахождению таких значений x и k, что 4∙x º 7∙k +1, где x и k – целые числа. Общая формулировка этой задачи – нахождение такого целого числа x, что

a∙x mod n =1, или a^–1 º x mod n

Решение этой задачи иногда существует, а иногда его нет. Например, обратная величина для числа 5 по модулю 14 равна 3, поскольку 5∙3=15 º 1 (mod 14). С другой стороны, число 2 не имеет обратной величины по модулю 14. Вообще сравнение a^–1 º x (mod n) имеет единственное решение, тогда и только тогда когда a и n – взаимно простые числа.

В этом случае говорят, что элемент a обратим и его обратный элемент a^–1 равен x. Часто элемент a^–1 часто обозначают через . Но надо всегда понимать, что это целый положительный вычет по модулю n. Множество всех обратимых элементов кольца Z/n называется мультипликативной группой кольца вычетов Z/n. Эту группу обозначают через G или (Z/n)*. Оказывается, что элементa из Z/n обратим, тогда и только тогда, когда он взаимно прост с n, (a,n)=1. Через обозначают, так называемую, функцию Эйлера, значение от натурального числа n равно числу положительных целых чисел меньших n и взаимно простых с n. В связи с чем, число |G| элементов в мультипликативной группе вычетов кольца Z/n равно , .

Пример. Пусть модуль n =10. Полный набор вычетов по модулю n =10 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Из них только 1, 3, 7, 9 не имеют общего сомножителя с числом 10, то есть обратимы, , G={1, 3, 7, 9}, |G|=4.

Для произведения простых чисел p, q

=n, |G|=

Модуль n	Функция j(n)
n – простое n2 … nr	n –1 n (n –1) … nr–1 (n – 1)
n= p∙q (p, q – простые) … n= (pi – простые)	(p – 1)(q – 1) … a

Любой элемент a из группы G порождает подгруппу H =<a>={a,a²,a³,…,a^m}

Относительно умножения по модулю n порядок группы =<a>={a,a²,a³,…,a^m} (число ее элементов), совпадает с порядком элемента a – наименьшим натуральным числом m, при котором a^m º1 (mod n). Для g из G и ее подгруппе H={h₁,h₂,.., h_m} положим gH={gh₁,gh₂,…gh_m}. Легко видеть, что |H|=|gH| и при g не принадлежащим H их пересечение пусто. Любая группа имеет разложение по левым (правым) смежным классам по своей подгруппе, G=e (G= ), e – нейтральный элемент (в нашем случае e=1). Классы – подмножества (попарно не пересекаются и в объединении дают G). Из сказанного следует, что k|H|=|G| (теорема Лагранжа), Положим H==<a>, <a>={a,a²,a³,…,a^m}. Тогда |H| в нашем случае совпадает с порядком элемента a, |H|= m, то m делит |G|=j(n). По этой причине а^j(n) =а^cm для некоторого с и а^j(n) =а^cm= º(1)^с(mod n) для любого элемента а из G. Таким образом, справедливы теоремы:

· малая теорема Ферма: если n– простое и НОД (a,n)=1, то a^n–1 º1 (mod n);

· теорема Эйлера: если НОД (a,n) =1, то a^j(n) º1 (mod n).

Основные способы нахождения обратных величин a^–1 º 1 (mod n).

1. Проверить поочередно значения 1, 2,..., n–1, пока не будет найден a^–1 º1 (mod n), такой, что a∙a^–1 (mod n) º 1.

2. Если известна функция Эйлера j(n), то можно вычислить a^–1 (mod n) º a^j(n)–1 (mod n), используя алгоритм быстрого возведения в степень.

3. Если функция Эйлера j(n) не известна, можно использовать расширенный алгоритм Евклида.

Проиллюстрируем эти способы на числовых примерах.

1. Поочередная проверка значений 1, 2,..., n – 1, пока не будет найден x = a^–1 (mod n), такой что a∙x º 1 (mod n).

Пусть n = 7, a = 5. Требуется найти x = a^–1 (mod n).

a∙ x º 1 (mod n) или 5∙x º 1 (mod 7).

Получаем x = 5^–1 (mod 7) = 3. Результаты проверки сведены в таблицу.

Нахождение a^–1 (mod n), если известна функция Эйлера j(n). Пусть n=7, a=5. Найти x=a^–1 (mod n)=5^–1 (mod 7). Модуль n=7 – простое число. Поэтому функция Эйлера j(n)=j(7)=n–1=6. Обратная величина от 5 по mod 7

a^–1 (mod n) = a^j(n)–1 (mod n) =

= 5^6–1 mod 7 = 5⁵ mod 7 = (5² mod 7)(5³ mod 7) mod 7 =

= (25 mod 7)(125 mod 7) mod 7 = (4 * 6) mod 7 = 24 mod 7 = 3.

Итак, x = 5^–1 (mod 7) = 3.

Нахождение обратной величины a^–1 (mod n) с помощью расширенного алгоритма Евклида. Пусть НОД(а,n)=1, a>0, n>0. Рассматривается задача поиска целочисленного решения (x,y) уравнения a∙x-n∙y=1. Для решения задачи используют сначала алгоритм Евклида:

a = n ∙q₀ + r₁

n = r₁ ∙ q₁ + r₂

r₁ = r₂ ∙ q₂ + r₃

r₂ = r₃ ∙ q₃ + r₄

…………………

r_k–2 = r_k–1 ∙ q_k-1 + r_k

r_k–1 = r_k ∙ q_k +0

Находят последовательность q₀, q₁, q₂,…,q_k. Затем рекуррентно строят P₀,Р₁,Р₂,…,Р_k и Q₀,Q₁,Q₂,…,Q_k. Полагают

P_-2=0, P_-1=1 и P_j=q_jP_j-1+ P_j-2 для j 0,

Q_-2=1, Q_-1=0 и Q_j=q_jQ_j-1+Q_j-2 для j 0.

Искомые значения x, y находятся по формулам

.

Обратный элемент а^-1= (modn) для числа а есть решение уравнения

Вычисления в конечных полях. Поле F есть множество, на котором определены операции сложения и умножения, удовлетворяющие требованиям: ассоциативности, коммутативности, дистрибутивности, существования аддитивного 0 и мультипликативной 1, аддитивных обратных и мультипликативных обратных для всех элементов за исключением 0. Примерами простейших конечных полей являются кольца вычетов по простому модулю Z/p.

Конечное поле F(q) с конечным числом q элементов играет важную роль в криптографии. В общем случае число элементов конечного поля имеет вид

q = pⁿ,

где p – некоторое простое число и n ³1. Конечные поля называют полями Галуа и обозначают GF(pⁿ) или GF(p) при n =1. Многие криптосистемы шифров с открытым ключом базируются на полях Галуа GF(p), где p – большое простое число.

Пример. Поле Галуа GF(5) имеет элементы 0, 1, 2, 3, 4 и описывается следующими таблицами сложения и умножения.

Если p – простое число, то число a Î{1,…, p –1} является взаимно простым с p, и поэтому обратный элемент a^–1 существует. Тем самым однозначно определяется операция деления.

Обозначим через GF*(p) множество всех ненулевых элементов поля GF(p). Некоторый элемент g из GF*(p) называют образующим или порождающим элементом GF*(p), если для всех a из GF*(p) найдется такое целое x, что g^x = a modp. Всего имеется j(p–1) образующих элементов g. Число x называют дискретным логарифмом элемента a по основанию g и модулю p. Вычисление дискретных логарифмов (когда заданы g, a и p) примерно такая же труднорешаемая задача, как и задача разложения целого числа на множители.

Существенный с точки зрения криптографии факт состоит в том, что не известно никакого эффективного алгоритма вычисления дискретных логарифмов. Более точно. Криптографическая стойкость ряда шифров с открытым ключом держится именно на отсутствии эффективного алгоритма вычисления дискретных логарифмов.