Home > CS178 > Homework 6

I didn't totally figure out multiplicative inverse till the end of OH Thursday, but to make it up to you, here's Curby's guide to multiplicative inverse

```> ...in the homework, it asks that we use k = 2, 3, 4, 5 for part 1.
> I get valid results for k=2, which then narrow down with k=3,
> and 4, but I don't get any valid results for k=5.  Is that a problem?

Remember that these intervals are around "good" ratios for omega and m.
When you incorporate more and more knapsack lengths, you gradually weed
out more bad intervals (bad ratios).  But there should always be at
least one good interval, because we expect that a ratio between omega and
m actually exists.  So no, you should never run out of intervals, even if
you consider all of the knapsack lengths.
```

```> There are 26 rows in the problem, so i think Bi & ti should be 26 in length.

This depends on mu.  I think you happen to be right, but you should not
count on this.

The number of bits you consider at any time is mu bits.  mu is the log
(base 2) of the sum of all your public knapsack elements.  Why?  When
encrypting, you consider a chunk of plaintext equal to the length of your
public knapsack (8 in this case).  For every '1' bit in that chunk of
plaintext, you add the corresponding knapsack value.  Refer to page 6 of
the reader.  The first chunk is

1 0 0 0 1 0 0 1

This corresponds to the first, fifth, and eighth knapsack values

1318 + 2428 + 284 = 4030

You add those together to get the first B, which is then represented in 15
bits (right column on page 6).

15 is mu, and you need 15 bits because if you had all 1s instead of the
10001001 pattern, you would need to add up all the ai values, and you
happen to need 15 bits to represent that sum.

> si should naturally be 8 bits in length, since it is the private knapsack.

That's right.  The private and public knapsacks are the same length.

> And when performing the ti - si step you should produce 8 bits in reverse
> order per row; one for each bit in si; Which would give me 208 bits (26 rows
> * 8 bits per row). See the note below for a more fitting answer

Ok the problem is that you're subtracting incorrectly.  What you will do
is something similar to the encryption process, but with the private
knapsack si.  Refer now to page 7.  You read in your 15 bits (because mu
is 15 in this case), and represent that in decimal: 4030, same as above.
Now you compute

t = (omega * B) mod m

Note: you can ignore and skip the third column (B^(i) mod m).  In this
case,

t = 2107

Now you start from the largest private knapsack value and try to subtract.
Whenever you can subtract a knapsack value without going negative, do so
and write a 1, otherwise you write a 0.

subtract      result             z
===========   ======             ========
2107 - 2005 = 102                       1
102  - 1003 = negative!                01
102  - 501  = negative!               001
102  - 100  = 2                      1001
2    - 22   = negative!             01001
2    - 11   = negative!            001001
2    - 6    = negative!           0001001
2    - 2    = 0                  10001001

Remember to work from least significant to most significant (right to
left).  The next 8 bits you get are added onto the right:

3533 - 2005 = 1528               10001001       1
1528 - 1003 = 525                10001001      11
525  - 501  = 24                 10001001     111
24   - 100  = negative!          10001001    0111
24   - 22   = 2                  10001001   10111
2    - 11   = negative!          10001001  010111
2    - 6    = negative!          10001001 0010111
2    - 2    = 0                  1000100110010111

When you are done, you will have a long string of bits.  Take them 7 at a
time and convert to their ascii equivs.
```
Note: If what Dr. Konheim is doing on the right side of page 7 confuses you, just ignore it. All you do is build up your string of bits by decrypting each chunk of mu bits like I do above. Then when you're done, read them all out 7 bits at a time. Done!

Note:I probably answered the wrong question. The extra bits at the end are due to padding: the plaintext must be padded with enough bits to make the plaintext a multiple of 8 bits long. So if you end up with extra bits at the end: Check to see if the deciphered plaintext looks complete. If so, then you probably didn't make a mistake, the extra bits are due to padding, and you can safely ignore them and end the decryption.
```> When solving for omega inverse, the notes say to find an integer that
> satisfies 1 = omega * omegaInverse (modulo m). Exactly what gets
> modulo'd, and when? (omega * 1/omega) mod m will always equal 1 for any
> number, as will (omega mod m) * 1 / (omega mod m).
> So I'm a bit confused... how exactly do you solve for this?

First of all, it's not really 1/omega, because that wouldn't be a natural
number (most likely).  In this context, omega^-1 is another way of saying

"Find some natural number, say x, that when multiplied by omega modulo m,
yields one.  Instead of throwing another variable into the mix, we can
just let x be called omega^-1 because it's kinda like a reciprocal, but
with natural numbers."

For example,

13*2 mod 25 = 1

omega    = 13
omega^-1 =  2
m        = 25

Hopefully that makes a bit of sense.  As to the calculation of it...

refer to http://www.cs.ucsb.edu/~kirbysdl/cs178/multinv.html

for one way to do it.  You can brute force it, but you'll need to do
something similar but with bigger numbers (i think) for another homework,
so just do it the "right" way.
```

```> After looking at your sample solution from last year Mike, a question came
> to mind....It looks as if you have many different M, omega, and omega-1
> values for the same interval....is this possible?

yup.  Remember your M values range from the largest a to four times that
value.  So even though you're weeding out a lot of possibilities using the
four tests, you still will have a bunch of Ms that do work. Or at least,
it is likely that you will have more than one.

So in the end, you will get different s arrays (private knapsacks).
That's why he says choose any two... the point is that any of those should
work... so choose two at random and decrypt to convince yourself!
```
Also, notice that Dr. Konheim has several M,Omega,Omega^-1 sets for the same interval on page 4 of shamirExample.pdf.
```>    I was wondering if we were only supposed to perform the 3 tests on the
> intervals found using all 5 of the k intervals, or are we supposed to do the
> 3 tests on every potential interval we find for k = 2, 3, 4, and 5
> intervals?  Thank you.

The point of doing all these intersections is that as we include more a_i
knapsack elements, we're performing more stringent tests.  The point is
that the correct interval will be in the intersection of all a_i
intervals, but we only consider the first 5 because that should be enough

Short answer: only look at the last set (when k=5).  In fact, only doing
the first interval for k=5 generally works for me (but you will have to
try other intervals if you don't get any good results for the first
interval).
```
```Exactly right.  And M starts at the largest `a' (public knapsack) value
and goes to 4 times the starting value.

See shamirExample.pdf on the class web site

On Fri, 9 May 2003, Ted Huffmire wrote:

> Omega is the integer you found
> to live in the interval when you
> multiplied the endpoints by M.
> You need to find the multiplicative
> inverse of Omega modulo M.
>
> See the following link for an explanation
> of the Euclidean method and source code in Java:
> http://www.math.ksu.edu/math791/monday/moddiv.html
>
> > Which two numbers do we use as input to calculate the multiplicative
> > inverse and the GCD?
```

```> Can we just check to see if a omega inverse exists (ie
> gcd = 1).  It says on the assignment that we have to
> display our results in a table like in the notes.  Is
> it ok to not compute the inverse since we dont need it
> anyway (or am I missing something and we do need it)
> and just leave that column in the table blank.

1) It's probably expected by Konheim, so I'd do it
2) It's around 15 lines of code, so I'd do it
3) you need it anyway in future homeworks, so I'd do it
4) Continuing from above, you might want to modularize your code so it's
easier to #include in your next homeworks.
```

```Ted's right.  While this isn't the way I do it, you can probably still do
it efficiently.  Remember to not actually compute all the different
possibilities, but rather stop the current iteration and "continue" when
you detect an empty intersection.

for all a_0
for all a_1
compute the a_0, a_1 intersection
if it fails
continue
else
for all a_2
compute...

... or something like that. YMMV, HTH, etc.

--Mike

(Ted please confirm that I'm not on crack).

On Thu, 8 May 2003, Ted Huffmire wrote:

> Date: Thu, 08 May 2003 16:41:51 -0700
> Subject: Re: project 6 program 1
>
> No you won't have to take thousands of years.
>
> Take a look at the pseudocode:
>
> http://www.cs.ucsb.edu/~konheim/CS178/KnapProg.pdf
>
> k=5 means you have 5 nested loops.
> there will be a loop for a0, a1, a2, a3, and a4.
> For aj's loop you try 0 to 0 + epsilon,
> 1/aj to 1/aj plus epsilon, ..., k/aj to k + epsilon, ...
> 1 - 1/aj to 1 - 1/aj + epsilon.
>
> btw, for modular division, see the following link:
>
> http://www.math.ksu.edu/math791/monday/moddiv.html
>
> Ted
>
> >
> > I have been programming program 1 and came to a problem.  To test for
> > (for example) k = 5, does that mean we will have 5 nested loops of
> > size 638, 3578, 971, 1942, 1388?  If this is the case then our program
> > will have to run through 638*3578*971*1942*1388 loops which is
> > 5974738975246624 loops!  This program will run for thousands of
> > years!!  Am I doing something wrong?  Thanks.
>

```
```> are you planning to post any notes on hw6 on your web site?