ВВЕДЕНИЕ
Задача о ранце (или задача о рюкзаке) – одна из задач комбинаторной оптимизации. Своё название получила от задачи укладки как можно большего числа ценных вещей в рюкзак, при условии, что вместимость рюкзака ограниченна. С различными вариациями задачи о ранце можно столкнуться в экономике, прикладной математике, криптографии и логистике[2].
В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничения на суммарный вес.
Задача о ранце в криптографии (англ. Knapsackproblem) – это задача, на основе которой американские криптографы Ральф Меркл и Мартин Хеллман разработали первый алгоритм шифрования с открытым ключом. Он носит название криптосистема Меркла-Хеллмана. Для шифрования сообщений использовалось решение задачи о рюкзаке. Потому, как считалось, она могла обеспечить криптостойкость системы.
Алгоритм:
Шифрование
1) Задаётся сверхрастущий вектор А вида(
), где каждый элемент вектора больше суммы предыдущих. Он является закрытым ключом. Вектор должен иметь такую же длину, как и количество бит в кодировке символов;
2) Находим m и t такое, что m больше суммы элементов вектора, а t является взаимно простым числом по отношению к m;
3) Вычисляем открытый ключ 
по формуле 
, где 
и 
– элементы векторов. Вектор В не является сверхрастущим;
4) Код буквы переводится в двоичное представление и скалярно перемножается на . Полученное число является зашифрованным сообщением (весом рюкзака);
5) Получателю передаются: шифрованное сообщение и открытый ключ () по открытому каналу, а числа m и t передаются по закрытому каналу[1].
Дешифрование
1) Получаем данные шифрованного сообщения;
2) Находим число u такое, что 
;
3) Отыскиваем новый вектор 
по формуле:
4) Вычисляем закрытый ключ по открытому ключу по формуле 
;
5) Определим исходный 
, зная 
, по формуле 
6) Имея и находим двоичные значения символа по известному алгоритму (
).
7) Решение получается просмотром рюкзачного 
справа на лево. Алгоритм нахождения двоичного кода исходного символа:
- Вводим величину к (объём рюкзака).
- Вводим сверхрастущий .
- Обнуляем значение исходного символа.
- Цикл перебора элементов идет от большего к меньшему.
- Сравниваем текущее значение рюкзака k и значения элемента 
.
- Если 
, то 0 отправляем в маску символа. Переходим в конец цикла.
- Если 
, то 1 отправляем в маску из значения k вычитаем объём (k- ).Переходим на конец цикла.
8) Считываем полученный результат снизу вверх – это двоичный вектор, который является кодом расшифрованного символа[3].
ПОСТАНОВКА ЗАДАЧИ
Используя рюкзачный метод шифрования, составить алгоритм и написать программу, позволяющую реализовывать шифрование и криптоанализ (дешифрование) в области заранее оговоренного алфавита, согласованного с легальным получателем. Отладить программу, подготовить инструкцию пользователя и руководство администратора.
Рекомендуется создание программы с графическим пользовательским интерфейсом.
Предполагается следующая логика работы программы:
1. Запускается программа и открывается главное меню, позволяющее выбрать режим шифрования или режим дешифрования.
2. При выборе соответствующего режима, открывается окно для ввода исходного (зашифрованного – при дешифровании) сообщения и при необходимости сверхрастущего вектора.Пользователь вводит сообщение, вектор-ключ и запускает процесс шифрования (дешифрования) В открытый канал связи передается шифрованное сообщение x и открытый ключ , который всем доступен.
В качестве секретного ключа для легального пользователя передается значение t и m.
3. Программа выдаёт зашифрованное (исходное) сообщение.
Пользователь может вернуться в главное меню или ввести иное сообщение и ключ.
ТАБЛИЦА ПЕРЕМЕННЫХ
| Название переменной | Тип данных | Комментарий |
| m | integer | Хранит число m |
| a,b | integer | Содержат данные для проверки на простые числа |
| t | integer | Хранит число t |
| NOD | integer | Наибольший общий делитель |
| i, j | integer | Число для итерации |
| k, k1, k2 | integer | Хранит шаг для генерации |
| sum | integer | Сумма всех элементов вектора |
| s | integer | Исходное сообщение |
| s1 | integer | Хранит разряд сообщения |
| u | integer | Хранит число u |
| text | string | Хранит сверхрастущий вектор |
| ch | string | Хранит преобразованное число в строку |
| s2 | string | Хранит исходное сообщение в двоичном виде |
| text1 | string | Зашифрованное сообщение (в модуле дешифрования) |
| text2 | string | Открытый ключ (в модуле дешифрования) |
| chislo | string | Хранит в двоичном виде |
| openkey | array[1..8] ofinteger | Хранит открытый ключ (в модуле шифрования) |
| V | array[1..8] ofinteger | Хранит вектор |
| kluch | array[1..8] ofinteger | Хранит ключ |
| shifr | array[1..100] ofinteger | Хранит зашифрованное сообщение |
| x | array[1..100] of integer | Хранит вектор
|
| ish | array[1..100] of integer | Хранит расшифрованное сообщение |
БЛОК-СХЕМА
Блок-схема 1 – Схема определения наибольшего общего делителя
Блок-схема 2 – Схема шифратора
Блок-схема 3 – Схема дешифратора
Блок-схема 4 – Схема работы приложения
ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ
Наименование программы:«Рюкзачный метод».
Программа написана в интегрированной среде Delphi.
Краткое описание:
Программа «Рюкзачный метод» позволяет шифровать и дешифровать информацию с использованием исходного (зашифрованного) сообщения, сверхрастущего вектора и при дешифровании дополнительных секретных параметров. Ввод информации может осуществлять на латинском и русском регистре.
Программа выполняет следующие функции:
- Шифрование исходного сообщения,
- Дешифрование зашифрованного сообщения.
Описание входных и выходных данных:
В режиме шифрования программа работает со строками исходного сообщения и сверхрастущим вектором, формируя зашифрованное сообщение.
В режиме дешифрования программа работает со строками зашифрованного сообщения, открытого ключа и секретными параметрами, формируя исходное сообщение.
Порядок работы с программой.
Инструкция содержать описание всех режимов работы программы, а также содержание всех выходных документов и диагностических сообщений, которые выдаются по ходу выполнения программы.
Программа запускается через файл Rukzak.exe, начальный экран программы содержит в себе весь функционал работы программы.При нажатии на кнопку «Выход», программа закрывается.
Продолжение работы с программой происходит с помощью навигационных кнопок, маркированных названием выполняемой функцией.
Шифрование исходного сообщения происходит при нажатие кнопки «Зашифровать». Открывается форма шифрования, в которой вводится исходное сообщение и при необходимости сверхрастущий вектор. После нажатия кнопки «Зашифровать» в соответствующем поле выводится зашифрованное сообщение. При этом секретные параметры m иt формируются программно.
При нажатии на кнопку «Главное меню», открывается главная форма приложения. Кнопка «Очистить», позволяет обнулить поля ввода.
Дешифрование зашифрованного сообщения происходит при нажатии кнопки «Дешифрование». Открывается форма дешифратора, в которую вводятся зашифрованное сообщение, открытый ключ и секретные параметры. После нажатия на кнопку «Расшифровать» выводится расшифрованное исходное сообщение в соответствующее поле. При нажатии на кнопку «Главное меню», открывается начальная форма приложения, соответственно при нажатии на кнопку «Очистить» произойдет обнуление полей.
Программа может выдавать ошибки при не корректном вводе данных, в этом случае данные не запишутся и необходимо повторить ввод.
Не корректный ввод исходного сообщения
Отсутствует пометка(v) для автоматического формирования вектора
Введен вектор имеет не корректные параметры
Восстановление работы программы после аварийного завершения не предусмотрено.Чтобы получить требуемый результат, достаточно следовать инструкциям программы и не допускать ошибок в работе.
Чтобы правильно завершить работу с программой необходимо нажать на кнопку «Выход».
РУКОВОДСТВО АДМИНИСТРАТОРА
1. Наименование программы;
Программа Delphi «Рюкзачный метод».
2. Описание программы;
Позволяет шифровать исходные сообщения и дешифровать зашифрованные сообщения с векторов и секретных параметров.
3. Запуск программы;
a. Запустите Rukzak.exe
b. Приложение запустилось. Для закрытия нажмите кнопку «Выход».
ЗАКЛЮЧЕНИЕ
Актуальность прохождения данной учебной практики заключается в закреплении и усовершенствовании навыков по профессии программиста.Во время прохождения практики был закреплен навык работы в интегрированной среде Delphi. В рамках данной работе мне было поручено задание программы «Рюкзачный метод шифрования»с графическим пользовательским интерфейсом.Выполняя задание, возникали ошибки, которые успешно были устранены. На данной практики я получила большой опыт программирования и усовершенствовала свои навыки.
На учебной практике проводилось ознакомление среализацией простых алгоритмов криптографии существующих в современных информационных системах.
Изучалась структура и принципы шифрования, и криптоанализа (дешифрование) в области заранее оговоренного алфавита, согласованного с легальным получателем. Исследовались виды и способы реализации рюкзачного метода шифрования.
СПИСОК ИСТОЧНИКОВ
1 Алгоритм "укладки рюкзака" – URL:https://habr.com/ru/post/222577/
2 Задача о рюкзаке - URL: https://neerc.ifmo.ru/wiki/index.php?title=%
D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D1%8E%D0%BA%D0%B7%D0%B0%D0%BA%D0%B5
3 Алгоритм "укладки рюкзака" – URL: https://foxford.ru/wiki/informatika
/algoritm-ukladki-ryukzaka
4 Создание собственных подпрограмм в Delphi – URL: https://www.delphi-manual.ru/lesson9.php
5 Процедуры и функции в Delphi » DelphiComponent.ru – URL:https://delphicomponent.ru/108-procedury-i-funkcii-v-delphi.html
6 Функции и процедуры Delphi. Справочник.– URL: https://delphi.scps.ru/math/math5.htm
7 29. Свойства – Программирование в Delphi – URL: https://www.introligator.org/articles/1/29
ПРИЛОЖЕНИЕ А
Листинг главной формы:
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Label1: TLabel;
Button1: TButton;
Button2: TButton;
Label2: TLabel;
Button3: TButton;
Label3: TLabel;
Label4: TLabel;
Label5: TLabel;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
uses Unit2,Unit3;
{$R *.dfm}
// кнопкаШифрование
procedure TForm1.Button1Click(Sender: TObject);
begin
Form1.Hide;
Form2.Show;
end;
// кнопкаДешифрование
procedure TForm1.Button2Click(Sender: TObject);
begin
Form1.Hide;
Form3.Show;
end;
procedure TForm1.Button3Click(Sender: TObject);
begin
Form1.Close;
end;
end.
Листингформы «Шифротор»:
unit Unit2;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm2 = class(TForm)
Label1: TLabel;
Edit1: TEdit;
GroupBox1: TGroupBox;
CheckBox1: TCheckBox;
Edit2: TEdit;
GroupBox2: TGroupBox;
CheckBox2: TCheckBox;
Edit4: TEdit;
Edit3: TEdit;
Label2: TLabel;
Label3: TLabel;
Button3: TButton;
Label4: TLabel;
Label5: TLabel;
Memo1: TMemo;
Memo2: TMemo;
Label6: TLabel;
Label7: TLabel;
Button1: TButton;
Button2: TButton;
procedureFormClose(Sender: TObject; var Action: TCloseAction);
procedure CheckBox1Click(Sender: TObject);
procedure CheckBox2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form2: TForm2;
implementation
uses Unit1;
{$R *.dfm}
// определение наибольшего общего делителя
functionNOD(a,b:integer): integer;
varmin,i: integer;
begin
if a>b then min:=b else min:=a;
for i:=min downto 2 do
if ((a mod i)=0) and ((b mod i)=0) then
begin
NOD:=i;
exit;
end;
NOD:=1;
end;
// закрытиеформы
procedure TForm2.FormClose(Sender: TObject; var Action: TCloseAction);
begin
Form1.Show;
end;
// галочка "автоматическая генерация" у сверхрастущего вектора
procedure TForm2.CheckBox1Click(Sender: TObject);
begin
if CheckBox1.Checked then
edit2.ReadOnly:=true
else
edit2.ReadOnly:=false;
end;
// галочка "автоматическая генерация" у чисел M и T
procedure TForm2.CheckBox2Click(Sender: TObject);
begin
if CheckBox2.Checked then
begin
edit3.ReadOnly:=true;
edit4.ReadOnly:=true;
end
else
begin
edit3.ReadOnly:=false;
edit4.ReadOnly:=false;
end;
end;
// кнопка "Зашифровать"
procedure TForm2.Button3Click(Sender: TObject);
var i,j,k,sum,m,t,s,s1: integer;
V, kluch: array[1..8] of integer;
shifr: array[1..100] of integer;
text,ch,s2: string;
begin
// исходныйтекст
if edit1.Text='' then
begin
ShowMessage('Не введён исходный текст.');
exit;
end;
Randomize;
sum:=0;
text:='';
// генерация сверхрастущего вектора
ifCheckBox1.Checkedthen
begin
for i:=1 to 8 do
begin
V[i]:=sum+1+Random(100);
sum:=sum+V[i];
text:=text+IntToStr(V[i])+';';
end;
edit2.Text:=text;
end
// или проверка корректности ввода вектора
else
if edit2.Text='' then
begin
ShowMessage('Сверхрастущий вектор не введен. Введитевектор!');
exit;
end
else
begin
text:=edit2.Text;
k:=0;
if text[length(text)]<>';' then
text:=text+';';
for i:=1 to length(text) do
begin
if text[i]=';' then
begin
k:=k+1;
V[k]:=StrToInt(ch);
if V[k]<=sum then
begin
ShowMessage('Введённый вектор не сверхрастущий!');
exit;
end;
sum:=sum+V[k];
ch:='';
end
else
ch:=ch+text[i];
end;
end;
{считывание или генерирование t и m}
if CheckBox2.checked then
begin
m:=sum+Random(1000);
repeat
t:=Random(m-1)+1;
until NOD(m,t)=1;
edit3.Text:=IntToStr(m);
edit4.Text:=IntToStr(t);
end
else
begin
m:=StrToInt(edit3.Text);
ifm<=sumthen
begin
ShowMessage('M должно быть больше суммы всех элементов');
exit;
end;
t:=StrToInt(edit4.Text);
if NOD(m,t)>1 then
begin
ShowMessage('M и T не взаимно простые числа');
exit;
end;
end;
text:='';
// получение открытого ключа
fori:=1 to 8 do
begin
kluch[i]:=(V[i]*t) mod m;
text:=text+IntToStr(kluch[i])+';';
end;
Memo2.Clear;
Memo2.Lines.Add(text);
text:='';
// шифрование
for i:=1 to length(edit1.Text) do
begin
s:=ord(edit1.text[i]);
s1:=s;
s2:='';
while s1>0 do
begin
if (s1 mod 2)=0 then
s2:='0'+s2
else
s2:='1'+s2;
s1:=s1 div 2;
end;
while length(s2)<8 do
s2:='0'+s2;
shifr[i]:=0;
for j:=1 to 8 do
if s2[j]='1' then
shifr[i]:=shifr[i]+kluch[j];
text:=text+IntToStr(shifr[i])+';';
end;
Memo1.Clear;
Memo1.Lines.Add(text);
end;
procedure TForm2.Button1Click(Sender: TObject);
begin
Form1.Show;
Form2.Close;
end;
procedure TForm2.Button2Click(Sender: TObject);
begin
Edit1.Text:='';
Edit2.Text:='';
Edit3.Text:='';
Edit4.Text:='';
Memo1.Clear;
Memo2.Clear;
end;
end.
Листингформы «Дешифротор»:
unitUnit3;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm3 = class(TForm)
Label1: TLabel;
Label4: TLabel;
Edit1: TEdit;
GroupBox2: TGroupBox;
Label2: TLabel;
Label3: TLabel;
Edit4: TEdit;
Edit3: TEdit;
Button3: TButton;
Label5: TLabel;
Edit6: TEdit;
Button1: TButton;
Edit2: TEdit;
Button2: TButton;
procedure Button3Click(Sender: TObject);
procedureFormClose(Sender: TObject; var Action: TCloseAction);
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form3: TForm3;
implementation
uses Unit1;
{$R *.dfm}
// кнопка "Расшифровать"
procedure TForm3.Button3Click(Sender: TObject);
varopenkey,V: array[1..8] of integer;
shifr,x,ish: array[1..100] of integer;
i,j,k,k1,k2,t,m,u,mn: integer;
text1,text2,chislo,ch: string;
begin
// проверкаданных
if (edit1.Text='') or (edit6.Text='') or (edit3.Text='') or (edit4.Text='') then
begin
ShowMessage('Не все поля заполнены');
exit;
end;
//edit5.Text:='';
text1:=edit1.Text;
k1:=0;
if text1[length(text1)]<>';' then
text1:=text1+';';
// считывание зашифрованного сообщения
for i:=1 to length(text1) do
begin
if text1[i]=';' then
begin
k1:=k1+1;
shifr[k1]:=StrToInt(ch);
ch:='';
end
else
ch:=ch+text1[i];
end;
text2:=edit6.Text;
k2:=0;
if text2[length(text2)]<>';' then
text2:=text2+';';
// считывание открытого ключа
for i:=1 to length(text2) do
begin
if text2[i]=';' then
begin
k2:=k2+1;
openkey[k2]:=StrToInt(ch);
ch:='';
end
else
ch:=ch+text2[i];
end;
// считывание m и t
m:=StrToInt(edit3.Text);
t:=StrToInt(edit4.Text);
u:=1;
// получение u
while (t*u mod m)<>1 do
u:=u+1;
// получение вектора x штрих
for i:=1 to k1 do
x[i]:=shifr[i]*u mod m;
// получение сверхрастущего вектора
fori:=1 to 8 do
V[i]:=openkey[i]*umodm;
// расшифровкасообщения
for i:=1 to k1 do
begin
ish[i]:=0;
chislo:='';
k:=x[i];
for j:=8 downto 1 do
if k>=V[j] then
begin
k:=k-V[j];
chislo:='1'+chislo;
end
else
chislo:='0'+chislo;
mn:=1;
for j:=length(chislo) downto 1 do
begin
ifchislo[j]='1' then
ish[i]:=ish[i]+mn;
mn:=mn*2;
end;
end;
for i:=1 to k1 do
edit2.Text:=edit2.Text+chr(ish[i]);
end;
// призакрытииформы
procedure TForm3.FormClose(Sender: TObject; var Action: TCloseAction);
begin
Form1.Show;
end;
procedure TForm3.Button1Click(Sender: TObject);
begin
Form1.Show;
Form3.Close;
end;
procedure TForm3.Button2Click(Sender: TObject);
begin
Edit1.Text:='';
Edit2.Text:='';
Edit3.Text:='';
Edit4.Text:='';
Edit6.Text:='';
end;
end.
ПРИЛОЖЕНИЕБ
Рисунок 1 – Форма главного меню
Рисунок 2 – Форма шифратора
Рисунок 3 – Форма дешифратора