Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I need to convert a hard knapsack to a superincreasing knapsack.

I have these superincreasing values (3,6,11,22,43,87). I also have w = 7 and n = 173. I converted the superincreasing values to hard one (21,42,77,154,128,90) by computing $a_i = x_i * w \bmod{n}$.

(3 * 7) mod 173 = 21
(6 * 7) mod 173 = 42
(11 * 7) mod 173 = 77
(22 * 7) mod 173 = 154
(43 * 7) mod 173 = 128
(87 * 7) mod 173 = 90

Question

I want to ask how can I get the superincreasing values if I have hard one.

example

Can I convert (21,42,77,154,128,90) to (3,6,11,22,43,87) with $w = 7$ and $n = 173$? Or how can I find the x_i if w = 7 and n = 173?

(x1 * w) mod n = 21
(x2 * w) mod n = 42
(x3 * w) mod n = 77
(x4 * w) mod n = 154
(x5 * w) mod n = 128
(x6 * w) mod n = 90
share|improve this question

1 Answer 1

up vote 1 down vote accepted

Here's the idea: given $w$ and $n$, we find a number $v$ such that $vw \equiv 1 \pmod{n}$. In your case of $w=7$ and $n=173$, we have $v=99$; such a $v$ will always exist if $w$ and $n$ are relatively prime, and can be found by the extended Euclidean algorithm. The value $v$ allows us to map from the "hard values" to the "superincreasing ones".

Here's how it works, suppose someone wants to send you a message corresponding to the first, third and fifth indicies: to encrypt it, he takes the public key, looks up the first, third and fifth indicides and adds them $21 + 77 + 128 = 226$; he sends the value $226$ as the ciphertext.

What you (the holder of the private key) would do is multiply the ciphertext (226) by $v$ modulo $n$; that gives $226 \times 99 \equiv 57 \pmod{173}$. You then go through the original superincreasing list to decode that, and easily see that $57 = 43 + 11 + 3$; that is the first, third and fifth indicies, correctly decoding the message.

This decoding method works quite well -- the problem with this crypto system is that it can be broken; this paper shows how an attacker can quickly decode even without the private key.

share|improve this answer
    
Thank you for your response. The problem is not how i encrypt/decrypt the message. The problem is if i have the hard one and the w = 7 and n = 173, how i find the superincreasing one? forget the message... i just want to find the superincreasing if i have the hard values. –  Ind F. Ashiku May 19 at 13:35
    
@IndF.Ashiku: that's easy; just take your hard sequence, and multiply each member by $v \bmod n$ -- that'll recover the original superincreasing sequence. For example, $(21 \times 99) \bmod 173 = 3$ and $(42 \times 99) \bmod 173 = 6$ –  poncho May 19 at 13:51
    
Thank you @poncho, that is the answer i was looking for :) –  Ind F. Ashiku May 20 at 10:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.