Discrete logarithm diophantiness.pdf Дискретный логарифм является важным математическим понятием в криптогра-фии. Существует множество криптографических протоколов, основанных на трудно-сти его нахождения. Достаточно упомянуть протокол разделения секретного ключаДиффи и Хеллмана, протоколы Масси - Омуры и Эль Гамаля. Многие протоколыаутентификации и цифровые подписи также имеют в основе дискретный логарифм.Цель данной работы - дать представление дискретного логарифма в ZP как ди-офантова множества, а также выписать явное представление соответствующего дио-фантова многочлена. Тогда проблема нахождения дискретного логарифма будет экви-валентна проблеме нахождения решения диофантова многочлена. Поскольку по зна-менитой теореме Ю. В. Матиясевича (решение 10-й проблемы Гильберта) проблемасуществования решения произвольного диофантова уравнения алгоритмически нераз-решима [1-3], указанная задача вычислительно трудна.Определение 1. Множество S С Zn является диофантовым, если существуетмногочлен D с целыми коэффициентами, такой, что(ab ... ,an) G S ^^ 3x1,... ,xm {D(ab ... ,an,x1,... ,xm) = 0}.Определение 2. Функция f : ZN ^ Z является диофантовой, если ее графикГ/ = { ( f (b1,... , bn), b1,... , bn) : (b1,... , bn) G dom f} является диофантовым множе-ством.Теорема 1. Пусть даны i,p,n G N, p простое. Тогда если следующая систе-ма уравнений имеет решение в натуральных числах в оставшихся аргументах, тоnk = i (mod p):'x2 - (a2 - 1)y2 = 1,u2 - (a2 - 1)v2 = 1,s2 - (b2 - 1)t2 = 1,v22 = 2r y2,b = 1 + 4yo = a + qu,s = x + cu,< t = k + 4(d - 1)y,y = k + e - 1,(x - y(a - n) - m)2 = (f - 1)2(2an - n2 - 1)2,m + g = 2an - n2 - 1,w = n + h = k + l,a2 - (w2 - 1)(w - 1)2z2 = 1,m = i + p j.Верно и обратное: если nk' = i (mod p) для некоторого k' G N, то эта системауравнений имеет решение в натуральных числах, причем k = k' (mod p - 1).Следствие 1. Дискретный логарифм в Zp является диофантовой функцией.Заметим, что данное представление может быть основанием протоколов разделе-ния ключа, аутентификации, цифровой подписи и т. п. Кроме того, оно может бытьиспользовано с целью организации атаки на дискретный логарифм.

Скачать электронную версию публикации