Криптосистема М2 Уильямса (Williams) 1980

•Криптосистема Рабина имеет недостаток, заключающийся в неоднозначности дешифрования криптограммы. Этот недостаток преодолевается в М2 Уильямса.

Генерирование ключей:

•	1) необходимо генерировать два простых числа р и q примерно
	одинаковой разрядности p ≡ 3(mod 8 ), q ≡ 7(mod 8 );
•	2) вычислить N = pq
•	3) выбрать в качестве открытого ключа		( N ,2 )	, а в качестве
	закрытого d.	d = ( p −1)( q −1) +1
		4

Шифрование

Пусть сообщение М удовлетворяет условию:

2(	2M +1
	2M +1) ≤ N, если cимвол Якоби	N	= −1
		2M	+1	=1
4( 2M +1) ≤ N, если cимвол Якоби		N

Шифрование выполняется в два шага:
1.			2M +1
	2(		2M +1), если cимвол Якоби				= −1
					N
	M ′ = E1( M ) =				2M	+1
								=1
		4( 2M +1), если cимвол Якоби			N

2. C = (M ′)2 mod N

Дешифрование

Действия выполняются в обратном порядке:

1.

2.

M ′ = Cd mod N

M ′

4

−

1

, если M

′

≡ 0 mod 4

2

( N − M ′)

−1

4

, если M′ ≡1 mod 4

2

M =

M ′

−

1

2

, если M

′ ≡ 2 mod 4

2

( N − M ′)

2

−1

, если M′ ≡ 3 mod 4

2

Показано, что стойкость криптосистемы Уильямса эквивалентна разложению N на множители.

Дополнения

Бывают криптосистемы :

•Рабина M 3 с соотношением 9:1 между открытыми текстами и шифротекстами.

•Уильямса M 3, которая устраняет эту проблему.