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.

×

## 2 Suggested Answers

Hi,
a 6ya expert can help you resolve that issue over the phone in a minute or two.
Best thing about this new service is that you are never placed on hold and get to talk to real repairmen in the US.
the service is completely free and covers almost anything you can think of.(from cars to computers, handyman, and even drones)
click here to download the app (for users in the US for now) and get all the help you need.
Goodluck!

Posted on Jan 02, 2017

See if this link helps

Posted on Jun 01, 2014

×

my-video-file.mp4

Complete. Click "Add" to insert your video.

×

## Related Questions:

### What are the major steps taken by Kurud Minister of Chhattisgarh towards the development of kurud?

The Kurud Minister in Chhattisgarh, Ajay Chandrakar reviewed the development works. All district panchayats must cooperate for the successful implementation of Mahatma Gandhi NREGA work. The employment-oriented functions should be also made accessible to those who need more jobs. As Mr. Chandrakar is the head of the department so he has reviewed the development of effective implementation of the government's welfare schemes and programs directed to the benefit of the public.

Jan 11, 2017 | Computers & Internet

Tip

### How to protect a mobile app and ensure user data privacy

After Edward Snowden case, the entire world became highly concerned about mobile app security and user data privacy. Especially it concerns mobile messengers with multiple user communications, data views, hacks, and so on.

For example, in 2016 WhatsApp popular messenger decided to fully encrypt the app and provide the complete protection by adding the end-to-end encryption (E2EE).

A bit later Viber also came to E2EE implementation, making it impossible for anyone (including themselves) to even view user information.

End-to-end is the system, in which devices transmit encrypted information to each other without third-party participation. Thus, the communication is direct, there are no intermediaries, and all the information, involving messages, calls, images, and video, is completely encrypted. Only those users who participate in the chat (one-to-one chats, group chats) will be able to read the messages.

It is based on public key encryption, working based on two keys - public and private. The first key (public) is used for encrypting messages and the second (private) - for their decryption.

An advantage is that a public key can be freely distributed, so everyone to whom a user gives your public key, can send an encrypted message. And since only he / she has a private key, only he / she can decrypt a message.

Find out more about E2EE and the ways to successfully encrypt a mobile app.

Whatsapp adds end to end encryption
Viber adds end to end encryption and hidden chats as messaging app privacy... Mobile app security Using end2end encryption for protecting mobile...

on Nov 06, 2017 | MoonBeam Development Android Apps

### What difference between genricServlet and httpServlet

public abstract class GenericServlet extends java.lang.Object implements Servlet, ServletConfig, java.io.Serializable
• GenericServlet defines a generic, protocol-independent servlet.
• GenericServlet gives a blueprint and makes writing servlet easier.
• GenericServlet provides simple versions of the lifecycle methods init and destroy and of the methods in the ServletConfig interface.
• GenericServlet implements the log method, declared in the ServletContext interface.
• To write a generic servlet, it is sufficient to override the abstract service method.
javax.servlet.http.HttpServlet
Signature: public abstract class HttpServlet extends GenericServlet implements java.io.Serializable
• HttpServlet defines a HTTP protocol specific servlet.
• HttpServlet gives a blueprint for Http servlet and makes writing them easier.
• HttpServlet extends the GenericServlet and hence inherits the properties GenericServlet.

May 12, 2011 | Computers & Internet

### I need to write a program in c implementing the merklehellman knapsack algorithm.please help me

Find a document describing the algorithm.
Find a textbook that teaches how to program in the C language.

Mar 03, 2011 | Computers & Internet

### Write an algorithm for the implementation of a circular doubly linked list

Write an algorithm for the implementation of a circular doubly linked list.

Feb 19, 2011 | Computers & Internet

### 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

### Hello,

try CC+ code....

Feb 28, 2009 | Computers & Internet

#### Related Topics:

1,319 people viewed this question

## Ask a Question

Usually answered in minutes!

Level 3 Expert

Level 2 Expert