2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Протокол Anshel–Anshel–Goldfeld
Сообщение09.12.2013, 15:11 
Добрый день
Нужна помощь в разборе протокола (http://en.wikipedia.org/wiki/Anshel%E2% ... y_exchange).
В кратце алгоритм:
Выбираем $G$ - некоммутативную группу, выбираем две системы образующих $(a_1,a_2, ... a_n)$ и $(b_1,b_2, ... b_n)$ для подгрупп $G_a,G_b$ соответственно.
Алиса выбирает случайное A, полученное комбинацией образующих (и их обратных).
Отправляет Бобу последовательность ($A^{-1}b_1A,A^{-1}b_2A,... $)
Боб выполняет аналогичные действия.
Как получить конечный общий ключ я не понял.
спасибо

 
 
 
 Re: Помогите разобраться в протоколе Anshel–Anshel–Goldfeld
Сообщение09.12.2013, 15:24 
Аватара пользователя
Преобразование $x\mapsto A^{-1}xA$ --- автоморфизм. Поэтому имея полученные от Алисы значения и зная $B = \prod b_{i_k}$, Боб сможет получить $A^{-1}BA = \prod (A^{-1}b_{i_k}A)$ и вычислить коммутатор. Аналогично, зная структуру $A$ и получив значения $B^{-1}a_iB$ от Боба, Алиса сможет вычислить $B^{-1}AB$.

 
 
 
 Re: Помогите разобраться в протоколе Anshel–Anshel–Goldfeld
Сообщение09.12.2013, 15:43 
Xaositect, спасибо
можно ли на примере?
пусть образующие $G_a$: ($a_1, a_2, a_3, a_4$), $G_b$: ($b_1,b_2,b_3,b_4$).
Алиса выбрала $A=a_1^{-1}a_3$, Боб выбрал $B=b_2b_4$.
Алиса отправляет последовательность ($A^{-1}b_1A,A^{-1}b_2A,A^{-1}b_3AA^{-1}b_4A$)
Боб отправляет последовательность ($B^{-1}a_1B,B^{-1}a_2B,B^{-1}a_3B,B^{-1}a_4B$)

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group