Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Криптосистема Merkle-Hellman

No description
by

Мишурова Таня

on 25 February 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Криптосистема Merkle-Hellman

Криптосистема
Merkle-Hellman
Пример
Программа
using System;
namespace Merkle_Hellman
{class Mercle_Hellman
{ static void Main(string[] args)
{ int[] w = { 2, 7, 11, 21, 42, 89, 180, 354 };
int q = 881;
int r = 588;
int[] beta = GetPublicKey(w, q, r);
Console.Write("Enter string to be encoded : ");
string plainText = Console.ReadLine();
int[] encoded = Encrypt(plainText, beta);
Console.WriteLine("\nThe encoded string is :\n");
int count = 0;
for (int i = 0; i < encoded.Length; i++)
{ Console.Write("{0, 5}", encoded[i]);
count++;
if (count == 16)
{ count = 0;
Console.WriteLine(): }}
if (count > 0) Console.WriteLine();
string decoded = Decrypt(encoded, w, q, r);
Console.WriteLine("\nThe decrypted string is : {0}", decoded);
Console.ReadKey(); }
static int[] GetPublicKey(int[] w, int q, int r)
{ int[] beta = new int[w.Length];
for(int i = 0; i < w.Length; i++) beta[i] = w[i] * r % q;
return beta; }
static int[] Encrypt(string plainText, int[] beta)
{ if (String.IsNullOrEmpty(plainText)) return null;
int[] encoded = new int[plainText.Length];
for(int i = 0; i < encoded.Length; i++)
{ string bin = ConvertToBinary(plainText[i]);
int sum = 0;
for(int j = 0; j < 8; j++) sum += (bin[j] - 48) * beta[j];
encoded[i] = sum; }
return encoded; }
Программа
static string Decrypt(int[] encoded, int[] w, int q, int r)
{ if (encoded == null || encoded.Length == 0) return null;
char[] chars = new char[encoded.Length];
int mir = ModInverse(r, q);
if (mir == 0)
{ Console.WriteLine("Modular inverse does not exist. Decryption aborted");
return null; }
for(int i = 0; i < encoded.Length; i++)
{ char[] bin = new char[8];
for(int j = 0; j < 8; j++) bin[j] = '0';
int temp = encoded[i] * mir % q;
while(temp > 0)
{ int index = 7;
for(int j = 1; j < w.Length; j++)
{ if(w[j] > temp) { index = j - 1; break;}}
bin[index] = '1'; temp -= w[index]; }
chars[i] = ConvertFromBinary(new string(bin)); }
return new string(chars); }
static string ConvertToBinary(char c)
{ return Convert.ToString((int)c, 2).PadLeft(8, '0'); }
static char ConvertFromBinary(string bin)
{ return (char)Convert.ToInt32(bin, 2); }
static int ModInverse(int r, int q)
{ int i = q, v = 0, d = 1;
while (r > 0)
{ int t = i/r, x = r;
r = i % x; i = x; x = d; d = v - t * x; v = x; } v %= q;
if (v < 0) v = (v+q) % q; return v;} } }
(продолжение)
Результат
Ранцевая криптосистема Меркла-Хеллмана, основанная на «задаче о рюкзаке», была разработана Ральфом Мерклем и Мартином Хеллманом в 1978 году. Это была одна из первых криптосистем с открытым ключом, но она оказалась криптографически нестойкой и, как следствие, не приобрела популярности.
Описание
Шифрование
– сообщение x = (x1, x2, ..., xn)
- вычисляем y = b1x1 + b2x2 + , ..., + bnxn
«Задача о рюкзаке» заключается в следующем: зная подмножество грузов, уложенных в ранец, легко подсчитать суммарный вес, но, зная вес, непросто определить подмножество грузов. Более подробно, пусть задана последовательность из n положительных чисел (n - "размер" рюкзака)
w = (w1, w2, ..., wn) и s.
Задача состоит в том, чтобы найти такой бинарный вектор
x = (x1, x2, ..., xn), (xi = 0 или 1),
чтобы
s=sum{i = 1..n} x_i*w_i.
Если каждому двоичному числу x поставить в соответствие некоторую букву алфавита, то её можно было бы передавать в зашифрованном виде просто как сумму s. Для произвольного набора чисел wi задача восстановления x по s является NP-трудной.

Р.Мерклю удалось получить обратную к числу s функцию, которая давала бы вектор x, зная только некий «секретный» ключ, и он предложил $100 тому, кто сможет раскрыть ранцевую систему Меркля-Хеллмана.
Описание
(продолжение)
Меркль использовал не произвольную последовательность wi, а супервозрастающую (superincreasing), то есть такую, что

w[k+1]>sum{i = 1..k} w_i
Нетрудно убедиться, что для такого набора чисел решение задачи является тривиальным. Чтобы избавиться от этой тривиальности и понадобилось ввести «секретный ключ», а именно два числа: q такое, что q>\sum_{i = 1}^n w_i и r такое, что НОД(r,q) =1. И теперь вместо первоначального набора чисел wi будем использовать числа bi=rwi mod q. В оригинальных статьях Меркль рекомендовал использовать n порядка 100, где n - число элементов супервозрастающей последовательности ("размер" рюкзака).
В итоге получаем: открытый ключ – (b1, b2, ..., bn), закрытый ключ - (w1, w2, ..., wn; q, r).
Расшифровка
- вычисляем s = yr-1 mod q
- решаем задачу для s для супервозрастающей последовательности (w1, w2, ..., wn), т.е. находим двоичное число x
Full transcript