The knapsack cryptosystem at work

This note is an example of the knapsack crypto-system at work.So before you got through this note I recommend reading the main one . Click here

Suppose that a typical user of this crypto-system selects as the secret key the super-increasing sequence 3,5,11,20,41{3,5,11,20,41} and the modulus m=85m = 85 and the multiplier a=44a = 44.Each member of the super-increasing sequence is multiplied by 44 and reduced modulo 85 to yield 47,50,59,30,19{47,50,59,30,19}.This is the encryption key the user submit to the public directory.

Suppose someone wants to send a plaintext message to the user such as "HELP US". First we convert it into a string of 1's and 0's M=0011100100010111010010010 M = 00111 00100 01011 10100 10010 The string is then broken up into blocks of digits,in the current case,blocks of length 5.Using the listed public keys to encrypt,the sender transforms the successive blocks into 470+500+591+301+191=10847*0+50*0+59*1+30*1+19*1 = 108 470+500+591+300+190=5947*0+50*0+59*1+30*0+19*0 = 59 470+501+590+301+191=9947*0+50*1+59*0+30*1+19*1 = 99 470+501+591+301+191=15847*0+50*1+59*1+30*1+19*1 = 158 471+500+591+300+190=10647*1+50*0+59*1+30*0+19*0 = 106 471+500+590+301+190=7747*1+50*0+59*0+30*1+19*0 = 77

The transmitted ciphertext consists of the following series of positive integers 108,59,99,158,106,777{108,59,99,158,106,777}.

To read the message the legitimate receiver first solves the congruence 44x1(mod85)44x \equiv 1 \pmod{85},yielding y29(mod85)y \equiv 29 \pmod{85}.Then each ciphertext number is multiplied by 29 and reduced modulo 85 to produce a super-increassing knapsack problem.

For example,108108 is converted to 7272 as 1082972(mod85)108*29 \equiv 72 \pmod{85} and the corresponding knapsack problem is 3x1+5x2+11x3+20x4+41x5=723x_1 + 5x_2 + 11x_3 + 20x_4+41x_5 = 72.

The procedure for solving super-increasing knapsack problems quickly yields the solution x1=x2=0x_1 = x_2 =0,x3=x4=x5=1x_3 = x_4=x_5 = 1,in this way 0011100111,the first block of the binary equivalent of the plaintext is obtained.

Note by Eddie The Head
5 years, 3 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link]( link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

How is the message' calculated? How "HELP US" is converted to given binary? I didn't get it. Please explain.

Muhammad Ali Makhdoom - 1 year, 1 month ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...