Crpytoanalysis of Merkle-Hellman Knapsack algorithm

opensourcenija
opensourcenija used Ask the Experts™
on
( 15 * q ) mod 17 = 1

I am trying to figure an easy wat to compute this , to find q . From the example i know q = 8 , but am finding a way how they were able to get to this answer.

detailed explanation will be appreciated
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Hi,

I don't know whether this is the kind of explanation you are expecting, but here goes:
If you look at the equation, it simply means that q is a number (integer in this case) which when multiplied by 15 and divided by 17 leaves 1 as remainder.

Manually, we needs to start counting from 1 onwards.
e.g.
(15*1) mod 17 = 15 mod 17 = ((17*0)+15) mod 17 = 15
(15*2) mod 17 = 30 mod 17 = ((17*1)+13) mod 17= 13
(15*3) mod 17 = 45 mod 17 = ((17*2)+11) mod 17 = 11

If you count in this manner, you'll see that the first number where the required condition (1 as remainder) is met is when q=8.
(15*8) mod 17 = 120 mod 17 = ((17*7)+1) mod 17 = 1

Speaking from the programming perspective, you can use the q as variable and state the equation as the condition which needs to be met, you'll get the same answer.

Hope this helps.

Warm regards,
Sarang

Author

Commented:
Yes but the fact is that I can't continue to test every possible number till i get a 8

am trying to derive a faster way of getting q.

because i am going to be dealing with larger interger values and it won't be possible for me to do that for all the values
( 15 * q ) mod 17 = 1
q = 15^(-1) mod 17; i.e., q is the modulo multiplicative inverse of 15 mod 17
Since 17 is prime (and therefore 15 and 17 are mutually prime, then we know that there exists a solution to this problem.

Here is an introduction to Modular multiplicative inverse:
http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

Here is code from http://snippets.dzone.com/posts/show/4256 on computing efficiently the modulo inverse (I did not test it):


int modInverse(int a, int n) {
 int i = n, v = 0, d = 1;
 while (a>0) {
  int t = i/a, x = a;
  a = i % x;
  i = x;
  x = d;
  d = v - t*x;
  v = x;
 }
 v %= n;
 if (v<0) v = (v+n)%n;
 return v;
}

Open in new window

Exploring ASP.NET Core: Fundamentals

Learn to build web apps and services, IoT apps, and mobile backends by covering the fundamentals of ASP.NET Core and  exploring the core foundations for app libraries.

Author

Commented:
Thanks for the input , but I am actually working this as a maths fomular with pen , paper and calculator and not writing a program
After getting problem in correct form, here is link showing Pen, paper, calculator example:
http://userpages.umbc.edu/~rcampbel/NumbThy/Class/BasicNumbThy.html#Modular-GCD
I'll be back later if you still need assistance.
Maybe this is clearer:

==
( 15 * q ) mod 17 = 1
-> 15q = 17k + 1
-> 15q - 17k = 1; solve for q
==
From the process described in http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm we get:
1 = 17(-1) + 15*8
If you let q=8 and k=1 you get 1 = 17(-k) + 15*q = 15*q - 17k
i.e., 1 = 15*q - 17k
and q = 8, the multiplicative inverse of 15 mod 17
Step 	Q 	Remainder 	Substitute 	Combine terms
1               17                              17 = 17*1 + 15*0
2               15                              15 = 17*0 + 15*1
3     17/15=1   2=17-15*1                        2 = 17*1 - 15*1
4     15/2 =7   1=15-2*7  = 15-(17*1-15*1)*7
                          = 15 -17*1 + 15*7      1 = 17(-1) + 15*8
5      2/1 =2   0            End of algorithm

Open in new window

Author

Commented:
good

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial