Алгоритм Шаміра

Шифр, запропонований Аді Шаміром (Adi Shamir), дозволяє організовувати обмін секретними повідомленнями відкритою лінією зв’язку для осіб, які не мають захищених каналів та секретних ключів.

Припустімо, два абоненти А та В сполучені лінією зв’язку (рис.). Абонент А хоче передати повідомлення М абонентові В у такий спосіб, щоб ніхто не дізнався про його зміст. Абонент А обирає випадкове велике просте число р і відкрито передає його абонентові В. Потім А обирає два числа – та такі, що

= 1 mod (p – 1).

Числа та є секретними. Абонент В теж обирає два секретні числа – та такі, що

1 mod (p – 1).

Після вибору чисел абонент А передає своє повідомлення М, використовуючи триступінчастий протокол. Якщо М < р (М розглядається як число), то повідомлення М передається одразу; якщо М > р, то повідомлення подається у формі М = , де усі < р, і потім передаються послідовно . При цьому для шифрування кожного оптимальніше буде обирати випадково нові пари (, ) та (, ) – інакше надійність системи знижуватиметься. Сьогодні такий шифр використовується здебільшого для передавання чисел, наприклад секретних ключів, значення яких є менше за р. Тому ми розглядатимемо лише випадок М < р. Подамо опис протоколу.

1) Абонент А обчислює число (mod p) і відкритою лінією зв’язку надсилає абонентові В.

2) Абонент В, отримавши , обчислює число (mod p) івідкритою лінією зв’язку надсилає абонентові А.

3) Сторона А обчислює число С (mod p) й передає його стороні В.

4) Сторона В, отримавши число С, обчислює повідомлення М C (mod p).

Дата добавления: 2015-05-08