fork download
copy 
  1. import java.util.*;
  2.  
  3. /**
  4.  * @see http://e...content-available-to-author-only...a.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem
  5.  */
  6. public class Main {
  7.  
  8.     // Extended Euclidean algorithm
  9.     private int eea(int e, int ph) {
  10.         int xprev = 1, x = 0;
  11.         int yprev = 0, y = 1;
  12.         int rprev = e, r = ph;
  13.         while(r != 0) {
  14.             int qnext = rprev / r;
  15.             int rnext = rprev % r;
  16.             int xnext = xprev - (qnext*x);
  17.             int ynext = yprev - (qnext*y);
  18.             xprev = x; x = xnext;
  19.             yprev = y; y = ynext;
  20.             rprev = r; r = rnext;
  21.         }
  22.         while(xprev < 0) {
  23.             xprev += ph;
  24.         }
  25.         return xprev;
  26.     }
  27.  
  28.     private void doIt() {
  29.         // First, a superincreasing sequence w is created
  30.         int[] w = { 2, 7, 11, 21, 42, 89, 180, 354, };
  31.  
  32.         // This is the basis for a private key. From this, calculate the sum.
  33.         int sum = 0;
  34.         for(int n : w) { sum += n; }
  35.  
  36.         // Then, choose a number q that is greater than the sum.
  37.         int q = 881;
  38.  
  39.         // Also, choose a number r that is in the range and is coprime to q.
  40.         int r = 588;
  41.  
  42.         // The private key consists of q, w and r.
  43.  
  44.         // To calculate a public key, generate the sequence β by multiplying each element in w by r mod q
  45.         int[] b = new int[w.length];
  46.         for(int i=0; i<b.length; i++) {
  47.             b[i] = w[i] * r % q;
  48.         }
  49.  
  50.         // Say Alice wishes to encrypt "a". First, she must translate "a" to binary (in this case, using ASCII or UTF-8)
  51.         char mes = 'a';
  52.         String str = Integer.toBinaryString(mes);
  53.         int sz = str.length();
  54.         for(int i=0; i<8-sz; i++) {
  55.             str = "0" + str;
  56.         }
  57.  
  58.         // She multiplies each respective bit by the corresponding number in β
  59.         int crypt = 0;
  60.         for(int i=0; i<b.length; i++) {
  61.             crypt += b[i] * (str.charAt(i) - '0');
  62.         }
  63.         int r1 = eea(r, q);
  64.  
  65.         // She sends this to the recipient.
  66.         // To decrypt, Bob multiplies 1129 by r^(-1) mod q
  67.         int decrypt = crypt * r1 % q;
  68.  
  69.         // Now Bob decomposes 372 by selecting the largest element in w which is less than or equal to 372.
  70.         // Then selecting the next largest element less than or equal to the difference, until the difference is 0:
  71.         // The elements we selected from our private key correspond to the 1 bits in the message
  72.         StringBuilder s = new StringBuilder("00000000");
  73.         for(int i=0; i<8; i++) {
  74.             if(decrypt >= w[8-i-1]) {
  75.                 s = s.replace(8-i-1, 8-i, "1");
  76.                 decrypt -= w[8-i-1];
  77.             }
  78.         }
  79.  
  80.         int num = Integer.parseInt(s.toString(), 2);
  81.  
  82.         // When translated back from binary, this "a" is the final decrypted message.
  83.         char res = (char)num;
  84.         System.out.println(res);
  85.     }
  86.  
  87.     public static void main(String[] args) {
  88.         new Main().doIt();
  89.     }
  90. }
Success #stdin #stdout 0.03s 245632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
a
https://ideone.com/VtgZq
language:
Java (HotSpot 12)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!