Пусть дано некоторое множество A={a1, a2, a3, … an} целых чисел и дано некоторое целое число C. необходимо найти некоторое подмножество элементов а, чтобы их сумма равнялась C, т.е. необходимо найти двоичный вектор М={м1, м2, …мn} mi=0 или 1, C=?miai i=1..n (*).
Например, а=(7,10,8,25,19,44); C=36 тогда вектор M=(1,1,0,0,1,0)
Разновидностью этой задачи является задача об укладке простого рюкзака.
Простым рюкзаком называется такая последовательность целых чисел А, в которой каждый следующий элемент больше суммы предыдущих, т.е. ai>?aj j=1..i-1. В случае простого рюкзака существование вектора м, удовлетворяющего условию (*) единственно.
Генерация открытого и закрытого ключа.
1)Выбирается простой рюкзак A={a1, a2, … an}
2)Выбирается некоторое число U>?ai i=1.. n
3)Выбирается целое число W взаимно простое с U, т.е. НОД(U,W)=1 и вычисляется обратное число W-1 . Оно определяется из условия
(W-1*W) mod U==1.
4)Последовательность А преобразуется в последовательность В в соответствии с правилом: bi = (Wai) mod U. Последовательность В- открытый ключ. Секретный ключ хранится у разработчика и состоит из 3-х элементов
(A, W-1, U).
Шифрование.
Абонент, обладающий открытым ключом, посылает второму некоторое n-битовое сообщение M={m1,m2,…,mn}. Для этого первый абонент вычисляет и посылает второму число C=?mi*bi i=1..n.
Расшифровка.
2-й абонент, получив C неходит число С’, C’=(W-1*c) mod U. Данное число С’ будет представлять собой ни что иное, как C’=?mi*ai , i=1..n, откуда и определяются значения mi, а следовательно и сами сообщения.
Пример: 1-й абонент выбирает простой рюкзак:
1.A={1, 4, 6, 13, 27}
2.?ai=51, U=69
3. W=13
4.W-1=?
(W-1*13) mod 59=1 => W-1=50
5. формируем открытый ключ В.
bi=(W*ai) mod U
b1=(13*1)mod 59=13
b2=(13*4)mod59=52
b3=(13*6)mod 59=19
b4=51; b5=56
B={13, 52, 19, 51, 56} -открытый ключ
А={1,4,5,13,27} и U=59 и W-1=50 –закрытый ключ.
Шифрование:
1-й абонент хочет послать 2-му некоторое сообщение M=(10011). Он вычисляет число C=?mibi , i=1..n. C=13+51+56=120
Данное число посылается второму абоненту.
Расшифровка:
Второй абонент вычисляет число C’: C’=120*50 mod 59=41
Используя последовательность А вычисляются
41=m1*1+m2*4+m3*6+m4*13+m5*27.
M=(10011)