Криптография с открытым ключом (несимметричные шифры). Однонаправленная функция и однонаправленная функция с секретом. Проблема существования однонаправленной функции

 

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

Однонаправленная функция: прямое преобразование в ней – это Р задача, а вот обратная функция к ней - это NP задача

Однонаправленная функция с секретом: прямое преобразование – это Р задача, а обратное NP задача, если неизвестен секрет, с помощью секрета обратная функция тоже сводится к Р задаче. (Очевидно, что вычисление секрета –это и есть NP-часть задачи)

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

 

Существование однонаправленных функций до сих пор не доказано. Если f является односторонней функцией, то нахождение обратной функции является трудновычислимой (по определению), но легкопроверяемой задачей (путем вычисления f на ней). Таким образом, из существования односторонней функции следует, что P ≠ NP. Однако, не известно, влечет ли за собой P ≠ NP существование односторонних функций. Современная асимметричная криптография основывается на предположении, что односторонние функции все-таки существуют.

 

Пример потенциально однонаправленной функции: возведение в квадрат по модулю. Обратная к ней функция – извлечение квадратного корня по модулю – это NP задача.

 

30. Целые числа: делимость, свойство евклидовости, алгоритм Евклида (с примером), расширенный алгоритм Евклида (с примером).

Дели́мость — одно из основных понятий арифметики и теории чисел, связанное с операцией деления. Если для некоторого целого числа и целого числа существует такое целое число , что то говорят, что число делится нацело на или что делит

При этом число b называется делителем числа a, делимое a будет кратным числа b, а число q называется частным от деления a на b.

Алгоритм Евклида – это способ нахождения наибольшего общего делителя двух целых чисел, а также наибольшей общей меры двух соизмеримых отрезков.

Чтобы найти наибольший общий делитель двух целых положительных чисел, нужно сначала большее число разделить на меньшее, затем второе число разделить на остаток от первого деления, потом первый остаток – на второй и т.д. Последний ненулевой положительный остаток в этом процессе и будет наибольшим общим делителем данных чисел.

Обозначив исходные числа через и , положительные остатки, получающиеся в результате делений, через , а неполные частные через , можно записать алгоритм Евклида в виде цепочки равенств:

Пример: a=54, b=15

a	b	r

НОД(54,15)=3

Расширенный алгоритм Эвклида:

Связан с так называемым соотношением Безу:

«Пусть a, b — целые числа, хотя бы одно из которых не нуль. Тогда существуют такие целые числа x, y, что выполняется соотношение: НОД(a,b) = x·a + y·b.»

Позволяет найти не только наибольший общий делитель. Но и числа x,y.

 

 

При этом значения x и y будут содержаться в x2 и y2 на том шаге, когда d окажется равным 0.

 

 

Пример: a=92, b=14

 

a	b	c	d	x1	x2	y1	y2
							-6
					-1	-6
				-1			-13

 

Проверка:

2=2*92-13*14; 2=184-182; 2=2