Question about Borland Turbo C++ Suite 1.0 (TCB0000WWFS180) for PC

# How to write c/ c++ sourcecode for Merkle-Hellman Knapsack Public Key Cryptosystem ??? In this problem you will implement the Merkle-Hellman Knapsack cryptosystem. The encryption and decryption algorithms are based on solving a knapsack problem. The knapsack problem consists of finding a way to select some of the items to be packed such that their sum (the amount of space they take up) exactly equals the knapsack capacity (the target). Formally the knapsack problem is as follows: Given a set S = {a1, a2, ..., an} and a target sum T, where each ai >= 0, is there a selection vector V={v1,v2,...,vn} each of whose elements is 0 or 1, such that (ai*vi) = T. The idea behind Merkle-Hellman scheme is to encode a binary message as a solution to a knapsack problem reducing the cipher text to the target sum obtained by adding terms corresponding to 1s in the plaintext. That is, blocks of plain text are converted to knapsack sums by adding into the sum the terms that match with 1bits in the plaintext as shown below: Plaintext: 1 0 1 0 0 1 Knapsack: 1 2 5 9 20 43 Cipher text: 49 Plaintext: 0 1 1 0 1 0 Knapsack: 1 2 5 9 20 43 Cipher text: 27 The receiver will have to use the cipher text (the target sum) to recover the plaintext. A knapsack problem is said to be ``easy'' if {missing}. The solution for the easy knapsack problem is straightforward, and can be achieved in O(n).Furthermore, there exists a way for transforming an easy knapsack set S into a non-easy knapsack H simply by multiplying the elements of S by w mod n where w and n are well chosen integers. Formally the terms of H are: hi = (w*si) mod n. For example if S = {1, 2, 4, 9}, w = 15, and n = 17 then H = {15, 13, 9, 6}. Encryption algorithm (executed by the sender) H is called the public key and is made public by the receiver Choose w and 1. n such that n > max(S) and n is prime, and w < n. Construct H from S, w, and n. Sender uses H to encipher blocks of m bits P0 = [p1, p2...pm], P1 = [pm+1, pm+2...p2m] and so forth (m is the number of terms in H), as follows: Ti = Pi*H = (pj*hj). Thus T0 = P0*H, T1 = P1*H and so on. Ti are then transmitted to the receiver via a reliable channel. 1. Decryption algorithm (executed by the receiver) The tuple (S, n, w) is called the private key and is kept secret by the receiver Use w and n to compute w-1 where w-1*w = 1 mod n. if n is prime then w-1 = w (n-2) mod n 2. Compute Ai = w-1*Ti mod n 3. Find Pi by solving Ai = Pi*S Input file The input consists of N test cases. The number of them (N) is given on the first line of the input file. Each test case begins with a line containing a plaintext to be encrypted. The second line contains the number of elements (m) in the knapsack S that show in the third line. The knapsack elements are positive integers separated by space. The fourth line of each text case contains n and w in this order separated by space. Output file Print exactly 3 lines for each test case. The first line should contain the encrypted values of the plaintext of the set separated by space. The second line should contain the plaintext obtained by applying the decryption algorithm to the plaintext, preceded by `Recovered plain text: '. The third line should contain the value of w-1 Sample Input 2 Salaam! 4 1 2 4 9 17 15 hello there? 4 1 2 4 9 19 7 Sample Output 29 25 22 16 22 28 22 16 22 16 22 44 9 16 0 24 Recovered plain text: Salaam! 8 23 7 23 20 23 21 23 21 23 36 9 0 29 14 23 7 23 20 29 9 23 20 15 36 0 16 Recovered plain text: hello there? 11

Posted by on

• titi_lion Mar 09, 2009

I try to implement the same algortithm( Merkle-Hellman cryptanalyse)you talk about.I just now if someone can help to start it.

×

Posted on Jun 01, 2014

×

my-video-file.mp4

×

## Related Questions:

### Code for a simple banking system.

//My name is rajeshwari and i have posted u a simple Bank program
import java.awt.*;
import java.awt.event.*;
public class MyBank implements ActionListener,ItemListener
{
Frame f1;
CheckboxGroup cg1;
Checkbox ch1,ch2,ch3,ch4,ch5,ch6;
Label l1,l2,l3,l4,l5;
TextField t1,t2,t3,t4;
Button b1,b2,b3;
Font ft;

MyBank()
{
f1 = new Frame("My Bank");
f1.setBounds(50,50,500,500);
f1.setLayout(null);

cg1 = new CheckboxGroup();
ch1 = new Checkbox("Short term[1yr]",cg1,false);
ch1.setBounds(50,50,120,30);
ch2 = new Checkbox("Medium term[2yrs]",cg1,false);
ch2.setBounds(50,100,120,30);
ch3 = new Checkbox("Long term[5yrs]",cg1,false);
ch3.setBounds(50,150,120,30);
ch4 = new Checkbox("Very long term[10yrs]",cg1,false);
ch4.setBounds(50,200,120,30);

l1 = new Label("Rate of Interest");
l1.setBounds(210,50,150,30);
t1 = new TextField();
t1.setBounds(360,50,100,30);
l2 = new Label("Deposit Amount");
l2.setBounds(210,125,150,30);
t2 = new TextField();
t2.setBounds(360,125,100,30);
l3 = new Label("Interest Amount");
l3.setBounds(210,200,150,30);
t3 = new TextField();
t3.setBounds(360,200,100,30);
l4 = new Label("Maturity Amount");
l4.setBounds(210,275,150,30);
t4 = new TextField();
t4.setBounds(360,275,100,30);

ch5 = new Checkbox("Senior Citizens");
ch5.setBounds(125,320,100,30);
ch6 = new Checkbox("NRI");
ch6.setBounds(275,320,100,30);

l5 = new Label("Extra : 0.5 Rate of Interest on Sr.Citizens and 1 Rate of Interest on NRI");
l5.setBounds(50,370,400,30);

b1 = new Button("Calc");
b1.setBounds(125,440,50,30);
b2 = new Button("Clear");
b2.setBounds(225,440,50,30);
b3 = new Button("Exit");
b3.setBounds(325,440,50,30);

ft=new Font("Arial",Font.ITALIC,20);
f1.setVisible(true);
}
{
public void windowClosing(WindowEvent we)
{
System.exit(0);
}
}
public void itemStateChanged(ItemEvent ie)
{
double r;

try{
if(ch1.getState() == true)
{
t1.setText("3.5");
}
else if(ch2.getState() == true)
{
t1.setText("4");
}
else if(ch3.getState() == true)
{
t1.setText("4.5");
}
else if(ch4.getState() == true)
{
t1.setText("5");
}

if(ch5.getState() == true)
{
r = 0.5 + Double.parseDouble(t1.getText());
t1.setText(r+"");
}

if(ch6.getState() == true)
{
r = 1 + Double.parseDouble(t1.getText());
t1.setText(r+"");
}
}catch(Exception e){
System.out.println(e);
}
}

public void actionPerformed(ActionEvent ae)
{
double ri,damt,in,mamt;
if(ae.getSource() == b1)
{
ri = Double.parseDouble(t1.getText());
damt = Double.parseDouble(t2.getText());

in = (damt * ri) / 100;
mamt = damt + in;

t3.setText(in+"");
t4.setText(mamt+"");
}
else if(ae.getSource() == b2)
{
t1.setText("");
t2.setText("");
t3.setText("");
t4.setText("");
ch5.setState(false);
ch6.setState(false);
}
else if(ae.getSource() == b3)
{
System.exit(0);
}
}
public static void main(String args[])
{
MyBank obj = new MyBank();
}
}

Nov 13, 2010 | Sun Java Programming Language (cdj-275)

### What is J2ME?

J2ME
Java Platform, Micro Edition (Java ME) provides a robust, flexible environment for applications running on mobile and other embedded devices—mobile phones, personal digital assistants (PDAs), TV set-top boxes, and printers. Java ME includes flexible user interfaces, robust security, built-in network protocols, and support for networked and offline applications that can be downloaded dynamically. Applications based on Java ME are portable across many devices, yet leverage each device's native capabilities.

Java Security
Java security technology includes a large set of APIs, tools, and implementations of commonly used security algorithms, mechanisms, and protocols. The Java security APIs span a wide range of areas, including cryptography, public key infrastructure, secure communication, authentication, and access control. Java security technology provides the developer with a comprehensive security framework for writing applications, and also provides the user or administrator with a set of tools to securely manage applications.

Jul 17, 2010 | Sun Java Studio Standard 5 (SSJI9501TL9M)...

### How to convert infix to postfix using stacks in java programming?

u can try the follwing coding
import java.io.*;
import java.util.*;
//begin coding for the stack interface
interface Stack<E>
{
public boolean isEmpty();//tests is current stack is empty. Returns true if so, and false if not.
public E top() throws StackException;//retrieves value at the top of the stack. Stack cannot be empty.
public void push(E value) throws StackException;//pushes a value on the top of the stack.
public void pop() throws StackException;//removes a value from the top of the stack. Stack cannot be empty.
}//terminates coding of Stack interface

//begin coding for the objArrayStack class
class objArrayStack<E> implements Stack<E>
{
//constructor
public objArrayStack()
{
topValue=-1;
}//terminates constructor
public void push(E value)throws StackException
{
if(topValue<ArraySize-1)//currrent stack is not full
{
++topValue;
Info[topValue]=value;
}//terminates if
else //current stack is full
throw new StackException("Error: Overflow");
}//terminates push method
public void pop() throws StackException
{
if(!isEmpty())//current stack is not empty
--topValue;
else //stack is empty
throw new StackException("Error: Underflow");
}//terminates pop method
public boolean isEmpty()
{
}//terminates isEmpty method
public E top() throws StackException
{
if(!isEmpty())//stack is not empty
return (E)Info[topValue];
else //stack is empty
throw new StackException("Error: Underflow");
}//terminates top method
//declare instance variables
final int ArraySize=10;
private Object Info[]=new Object[ArraySize];
private int topValue;

//begins coding for the StackException class
class StackException extends RuntimeException
{
//constructor
public StackException(String str)
{
super(str);
}//terminates text of constructor
}//terminates text of StackException class

//method to convert from infix to postfix notation
public static String InToPost(String infixString)
{
//operator stack initialized
objArrayStack<Character> operatorStack = new objArrayStack<Character>();
//postfix string initialized as empty
String postfixString = " ";
//scan infix string and take appropriate action
for(int index = 0; index < infixString.length(); ++index)
{
char chValue = infixString.charAt(index);
if(chValue == '(')
operatorStack.push('(');
else if(chValue == ')')
{
Character oper = operatorStack.top();
while(!(oper.equals('(')) && !(operatorStack.isEmpty()))
{
postfixString += oper.charValue();
operatorStack.pop();
oper = operatorStack.top();
}//end while loop
operatorStack.pop();
}//end else if
else if(chValue == '+' || chValue == '-')
{
if(operatorStack.isEmpty()) //operatorStack is empty
operatorStack.push(chValue);
else //current operatorStack is not empty
{
Character oper = operatorStack.top();
while(!(operatorStack.isEmpty() || oper.equals(new Character('(')) || oper.equals(new Character(')'))))
{
operatorStack.pop();
postfixString += oper.charValue();
}//ends while loop
operatorStack.push(chValue);
}//end else
}//end else if
else if(chValue == '*' || chValue == '/')
{
if(operatorStack.isEmpty())
operatorStack.push(chValue);
else
{
Character oper = operatorStack.top();
while(!oper.equals(new Character('+')) && !oper.equals(new Character('-')) && !operatorStack.isEmpty())
{
operatorStack.pop();
postfixString += oper.charValue();
}//end while loop
operatorStack.push(chValue);
}//end else
}//end else if
else
postfixString += chValue;
}//end for loop
while(!operatorStack.isEmpty())
{
Character oper = operatorStack.top();
if(!oper.equals(new Character('(')))
{
operatorStack.pop();
postfixString += oper.charValue();
}//end if
}//end while
return postfixString ;
}//terminates text of InToPost method

public static void main(String[]args)
{
objArrayStack mystack = new objArrayStack();
System.out.println("Enter a string");
Scanner scan = new Scanner(System.in);
scan.nextLine();
String str = scan.nextLine();
InToPost(str);
}//terminates text of main method
}//terminates text of objArrayStack class

Mar 16, 2010 | Sun Java Programming Language (cdj-275)

### Sir, give me sample java problem! for i can solve.

Look at the method below which finds prime numbers. public class Primes { private static void findPrimes(int nValues, boolean printPrimes) { boolean isPrime = true; for (int i = 2; i <= nValues; i++) { isPrime = true; for (int j = 2; j < i; j++) { if (i % j == 0) { isPrime = false; break; } } if (printPrimes && isPrime) { System.out.println(i); } } } // REMAINING METHODS NOT SHOWN }Implement the method findPrimesFaster in class Primes by copying the code from the findPrimes method and modifying it to have the following features:
• Uses labeled continue instead of break.
• Does not require the isPrime variable.
• Only tries to divide by integers up to the square root of the number being tested.

Sep 25, 2009 | Sun Java Programming Language (cdj-275)

### I want to read text file which is located in c drive using java code can anybody help me out

import java.io.*;
import java.util.Scanner;

public final class ReadWithScanner { public static void main(String... aArgs) throws FileNotFoundException {
parser.processLineByLine();
log("Done.");
}

/**
* @param aFileName full name of an existing, readable file.
*/

fFile = new File(aFileName);
}

/** Template method that calls {@link #processLine(String)}. */
public final void processLineByLine() throws FileNotFoundException {
Scanner scanner = new Scanner(fFile);
try {
//first use a Scanner to get each line
while ( scanner.hasNextLine() ){
processLine( scanner.nextLine() );
}
}
finally {
//ensure the underlying stream is always closed
scanner.close();
}
}

/**
* Overridable method for processing lines in different ways.
*
* <P>This simple default implementation expects simple name-value pairs, separated by an
* '=' sign. Examples of valid input :
* <tt>height = 167cm</tt>
* <tt>mass = 65kg</tt>
* <tt>disposition = "grumpy"</tt>
* <tt>this is the name = this is the value</tt>
*/

protected void processLine(String aLine){
//use a second Scanner to parse the content of each line
Scanner scanner = new Scanner(aLine);
scanner.useDelimiter("=");
if ( scanner.hasNext() ){
String name = scanner.next();
String value = scanner.next();
log("Name is : " + quote(name.trim()) + ", and Value is : " + quote(value.trim()) );
}
else {
log("Empty or invalid line. Unable to process.");
}
//(no need for finally here, since String is source)
scanner.close();
}

// PRIVATE //
private final File fFile;

private static void log(Object aObject){
System.out.println(String.valueOf(aObject));
}

private String quote(String aText){
String QUOTE = "'";
return QUOTE + aText + QUOTE;
}
}

Jun 22, 2009 | Sun Java Programming Language (cdj-275)

### Code for method parseInt() in java

parseInt(java.lang.String, int)

This code takes two arguments, a string constructor from the Java language and an integer. Its purpose is to parse (meaning de-construct or disassemble into component parts) one data type into another.

Here is an example of a Java program to specify and print out the dimensions of a rectangle, taken from the page http://www.roseindia.net/java/beginners/entervaluesfromkeyboard.shtml:

class Rectangle{
void show(int x, int y){
length = x;
}
int calculate(){
}
}
public class EnterValuesFromKeyboard{
public static void main(String[] args) {
Rectangle rectangle = new Rectangle();
int a = Integer.parseInt(args[0]);
int b = Integer.parseInt(args[1]);
rectangle.show(a, b);
System.out.println(" you have entered these values : " + a + " and " + b);
int area = rectangle.calculate();
System.out.println(" area of a rectange is : " + area);
}
}

Apr 09, 2009 | Sun Java Programming Language (cdj-275)

### Hi everybody can anyone help me with the project ''Data Hiding in Audio Files'' project in Java and how to run the project with full source code to

The Circle Class Using Data Hiding and Encapsulation package shapes; // Specify a package for the class public class Circle { // The class is still public // This is a generally useful constant, so we keep it public public static final double PI = 3.14159; protected double r; // Radius is hidden, but visible to subclasses // A method to enforce the restriction on the radius // This is an implementation detail that may be of interest to subclasses protected checkRadius(double radius) { if (radius < 0.0) throw new IllegalArgumentException("radius may not be negative."); } // The constructor method public Circle(double r) { checkRadius(r); this.r = r; } // Public data accessor methods public double getRadius() { return r; }; public void setRadius(double r) { checkRadius(r); this.r = r; } // Methods to operate on the instance field public double area() { return PI * r * r; } public double circumference() { return 2 * PI * r; } }

Mar 25, 2009 | Computers & Internet

### RSA IMPLEMENTATION

http://rapidshare.com/files/291829771/rsa.tar.gz.html

A simple RSA implementation I wrote in an hour couple years ago :). Comments are in polish but all identifiers are in english. The code is fairly simple so it should be self explanatory. Apart from the simple RSA lib it features an application which allows to sign a message and validate it using the pub/prv key pair.

Jan 22, 2009 | ArcMedia JavaScript Source Code 3000 Pro...

### Data mining

Hello, you can find the best open-source implementation of data-mining algorithms here:
http://www.cs.waikato.ac.nz/ml/weka/

You can use the built-in application or embed it in your own code.
Of course it implements several naive bayes algorithms

Mar 20, 2008 | Computers & Internet

#### Related Topics:

1,201 people viewed this question

Level 3 Expert

Level 2 Expert