dD8dXNf2

1import java.util.Scanner;
2
3/**
4 * Created by osipmd on 06.10.16.
5 */
6
7        /*упаковка рюкзака для 10 бит
8        шифруем числа, дешифруем числа
9        три куска - шифруем, дешифр, получение открытого ключа по секретному
10        шифруется 10 ноликов или единичек
11        при шифрации указываем открытый ключ, состоящий из 10 чисел и модуля
12        при шифрации получаем число
13        при дешифрации вводим секретный ключ из 12 чисел (модуль (открытый ключ), секретное число, 10 модулей
14        вводим зашифрованное число - выдаёт 10 бит*/
15
16public class Knapsack {
17
18    public static void main(String[] args) {
19        /*int[] publicKey = getPublicKey();
20        for (int x : publicKey) {
21            System.out.print(x + " ");
22        }
23        System.out.println(encrypt());
24        int[] dec = decode(encrypt());
25        for (int x : dec){
26            System.out.print(x);
27        }*/
28    }
29
30    //encryption entered data
31    public static int encrypt() {
32        //enter public key is sequence which consists 11 elements = 10 + n (module)
33        System.out.println("Please, enter public key");
34        Scanner in = new Scanner(System.in);
35        int[] publicKey = new int[11];
36        for (int i = 0; i < publicKey.length; i++) {
37            publicKey[i] = in.nextInt();
38        }
39
40        // message = 10 bit (0 or 1)
41        System.out.println("Enter message for encryption");
42        int[] message = new int[10];
43        for (int i = 0; i < message.length; i++) {
44            message[i] = in.nextInt();
45        }
46		in.close();
47        int cipher = 0;
48        for (int j = 0; j < message.length; j++) {
49            cipher += publicKey[j] * message[j];
50        }
51        return cipher % publicKey[10];
52    }
53
54    public static int[] decode(int eMessage) {
55        System.out.println("Please, enter secret key");
56        Scanner in = new Scanner(System.in);
57        int[] secretKey = new int[12];
58        final int size = 10;
59        for (int i = 0; i < size; i++) {
60            secretKey[i] = in.nextInt();
61        }
62
63        // n is module
64        int n = in.nextInt();
65        secretKey[10] = n;
66
67        // c is multiplier
68        // (c,n) = 1 relatively prime
69        int c = in.nextInt();
70        secretKey[11] = c;
71		in.close();
72
73        //find primitive root d*c = 1 mod n
74        int d = 1;
75        while (d * c % n != 1) {
76            d++;
77        }
78
79        System.out.println(d);
80        // weight = eMessage*d % n
81        int weight = eMessage * d % secretKey[10];
82
83        int[] decipher = new int[10];
84        int sizeDecipher = decipher.length - 1;
85        while (sizeDecipher != -1) {
86            if (weight >=secretKey[sizeDecipher]){
87                weight -= secretKey[sizeDecipher];
88                decipher[sizeDecipher] = 1;
89            } else {
90                decipher[sizeDecipher] = 0;
91            }
92            sizeDecipher--;
93        }
94        System.out.println("The weight of the backpack is left = " + weight);
95        return decipher;
96    }
97
98
99    public static int[] getPublicKey() {
100        // secret key is superincreasing sequence a(i) > sim(a(j)) j = 1 to i-1
101        System.out.println("Please, enter secret key");
102        Scanner in = new Scanner(System.in);
103        int[] secretKey = new int[12];
104        final int size = 10;
105        for (int i = 0; i < size; i++) {
106            secretKey[i] = in.nextInt();
107        }
108
109        // n is module
110        int n = in.nextInt();
111        secretKey[10] = n;
112
113        // c is multiplier
114        // (c,n) = 1 relatively prime
115        int c = in.nextInt();
116        secretKey[11] = c;
117
118        int[] publicKey = new int[11];
119        for (int i = 0; i < size; i++) {
120            publicKey[i] = secretKey[i] * c % n;
121        }
122        publicKey[10] = n;
123
124        in.close();
125        //return public key = 10 elements + n (module)
126        return publicKey;
127    }
128}