О криптографии

Открытая криптография

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

W. Diffie, M. Hellman,
"New directions in cryptography"

f(x) = a^x (mod p)

В 1976г. У.Диффи и М.Хеллманом было предложено использование односторонней криптографической функции f (a,p,x) где а, р - целые числа, обладающие рядом свойств. Прямое вычисление значения такой функции может быть произведено быстро - за доли секунды на современном компьютере. Нахождение х при известных а, р и значении f(x) является трудновыполнимой задачей, т,е. при определенных условиях (должным образом подобранных a,p) на ее решение понадобятся затраты в сотни миллионов долларов.

Тогда же была предожена идея электронной цифровой подписи (ЭЦП) — способа аутентификации автора документа по наличию у него индивидуального числа (ключа подписи x, который автор генерирует самостоятельно). ЭЦП формируется с применением этого индивидуального числа, а проверка ЭЦП — с применением другого числа (ключа проверки подписи f(x), связанного с ключом подписи). Таким образом, ЭЦП — аналог обычной подписи в следующем смысле:

подписать документ может только автор (владелец ключа подписи);
проверить подпись может любой, имеющий образец подписи автора (открытый ключ проверки подписи);
подделать подпись, имея образец, достаточно сложно (не легче, чем найти х в задаче Диффи-Хеллмана);
третьи лица изменить содержание документа, так, чтобы его юридическая сила осталась неизменной, не могут (процедура ЭЦП "связывает" ключ подписи, документ и собственно подпись);
процедура проверки авторства документа и соответствия его содержания индивидуальному ключу подписи должна давать возможность третьей стороне - например, хозяйственному суду, принимать решение о подлинности цифровой подписи и документа в случае возникновения конфликта.

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

R. Rivest, A. Shamir, L. Adleman
"A method for obtaining digital
signatures and public key cryptosystems"

p, q
n= pq
1 < e < (p-1)(q-1), [e,(p-1)(q-1)] = 1
d = e^-1 mod (p-1)(q-1)
E_{(n.e )}(x) = x^e modn, x
D_(d)(y) = y^d modn

Первым практическим решением задачи была так называемая "цифровая подпись RSA", разработанная в 1977 году в Массачусетском Технологическом Институте (США) и получившая свое название от первых букв фамилий авторов: R.Rivest, A.Shamir, L.Adleman. Их идея состояла в том, что, оперируя с большим целым числом n, которое является произведением двух различных больших простых чисел n = p*q можно легко подбирать пары целых чисел e, d, 1<e,d<n, так, что зная n и e, определить d будет не проще, чем разложить на множители число n, т.е. найти P и Q. В математике же с древних времен известно, что разлагать на множители целые числа из большого числа цифр (например, 100 или 200), это сложная вычислительная задача.

T. ElGamal
"A Public Key Cryptosystem and
a Signature Scheme Based on
Discrete Logarithms"
A.P.

Еще более сложная вычислительная задача, чем разложение на множители большого целого числа - задача дискретного логарифмирования. Метод цифровой подписи, надежность которого зависит от трудоемкости решения такой задачи, предложил американский ученый T.ElGamal в 1985 г.

Права на "цифровую подпись RSA" принадлежат частной компании "RSA DATA SECURITY". Более 15 лет понадобилось специалистам (а это небольшой срок для криптографии), чтобы оценить надежность предлагаемых алгоритмов и оформить их модификации в виде национальных стандартов некоторых стран.