Correction:
...bby the binomial theorem, (1+N)**N = 1 + N*N + other terms divisible...
I multiplied by N on the left when I ought to have exponentiated
Walter
On Mon, Sep 19, 2016 at 1:36 PM, Walter Ray-Dulany <raydul...@apache.org>
wrote:
> Hi Tim,
>
> Apologies! It's disorienting at first, and most of all when one actually
> tries to sit down and do a real example. The version on the slides was not
> written in one go, I assure you.
>
> Let's go through, and see what's not working.
>
> **************************
>
> > I'm trying a very simple example. I'm going to choose, p = 3, q = 5 and
> a message m = 42
>
> Already we're in trouble. p and q are fine; but remember that the
> plaintext space (let's call it P(N)) is the set of all integers in Z/NZ;
> that is, it is all numbers m
>
> 0 <= m < N
>
> You can see already that the m you chose is not in the plaintext space.
>
> Let's pick a new m to continue with; in this case, let's choose your m,
> but mod 15 so that it lies in P(N). Thus, our new m going forward shall be
>
> m = 12
>
> **************************
>
> > I'm going to pick g = 240. I think it needs to be a multiple of N that
> is greater than N*N, correct?
>
> No, and this is important. g has to be an element of (Z/(N squared )Z)* of
> order a nonzero multiple of N. That sentence is meaningless unless you're
> already embedded in the mathematics, so let's go through what it means, bit
> by bit.
>
> g must be:
> 1. *an element of (Z/(N squared)Z)**: everything but the outer * on the
> right just means that 0 <= g < N*N; in this case that means 0 <= g < 225.
> The outer * on the right indicates that we only want to take a certain
> special kind of g: one that is what we call a *unit* mod N*N; that is, it
> means that we require that there exist another element 0<= h < N*N such
> that g*h = 1 mod N*N. In our current situation, N = p*q is a product of
> primes, and so N*N = p**2 * q**2, and we can easily characterize G = (Z/(N
> squared)Z)*: G = { 0<= g < N*N such that neither p nor q divide g}. So as
> long as we pick a g that does not have p or q as a factor, we're good for
> this condition (this also includes 0, so really all of my "0 <=" in this
> paragraph could have been "0 < "). Another way to characterize G is to say
> that it is the set of integers less than N*N that are relatively prime to
> N*N.
>
> 2. *of order a nonzero multiple of N*: this is a little trickier. The
> *order* of an element g of a finite group (which G is) is the least
> integer k such that g^k = 1 in G. I'm not going to prove it here, but it
> turns out that every element of G has finite order (that is, if g is in G,
> then there exists a finite non-zero k such that g^k = 1), and that it is
> less than or equal to the Carmichael number lambda(N*N). That takes care of
> what 'order' means, and, like I said, order is defined for all g in G. But!
> We require a special order. Specifically, we only want g in G such that the
> order of g is a non-zero multiple of N. We might ask whether we know that
> such always exists (a good question, since we require it), and we do!
> Here's a quick proof of existence, one tied closely to Wideskies:
>
> * Take g = 1 + N (I'm going to prove, all at once, that 1+N is in G and
> that it has an order that fits the bill).
> * Consider g**N: by the binomial theorem, (1+N)*N = 1 + N*N + other terms
> divisible by N*N. This number is equivalent to 1 mod N*N. QED
>
> Ok, great, such g exist, and so we can require that we use one of them.
> But you must be careful: you can't just choose any g in G off the street
> and expect it will satisfy our requirements. You chose g = 240, which (1)
> bigger than N*N, which isn't what we want, and (2) is divisible by N, and
> so even if we take 240 mod N*N, we still aren't in G, much less of the
> 'right order' (turns out 240, being not relatively prime to N, can never be
> exponentiated to 1 mod N*N). For now, let's just take the standard
> Wideskies g, g = 1 + N = 16. If you want to go through this with a
> different g, give it a shot, but make sure it's got the right kind of order.
>
> **************************
>
> > I'll pick zeta = 21. I think it needs to be greater than N.
>
> As in point 2, no. We require zeta to be in (Z/NZ)*, which, similar to the
> above, means a number
>
> 0 < zeta < N such that zeta is a unit.
>
> You picked 21; if we take 21 mod N we get zeta = 6, which is not a unit
> (in particular it is not relatively prime to p=3). Let's pick the next
> number greater than 6 which is in (Z/NZ)*, which is
>
> zeta = 7.
>
> **************************
>
> Let's see what we've got.
>
> ( (16**12)*(7**15) ) mod 225 = 208.
>
> I will leave it as an exercise to check that the decryption of 208 is in
> fact 12.
>
> **************************
>
> Ok, that's all so far. If the above is still not computing (literally or
> metaphorically), I am available to converse one-on-one either over the
> phone or some other medium (face time or what have you) and only too happy
> to go over this more.
>
> Let me know,
>
> Walter
>
>
>
> On Mon, Sep 19, 2016 at 12:13 PM, Tim Ellison <t.p.elli...@gmail.com>
> wrote:
>
>> On 17/09/16 06:42, wraydulany wrote:
>> > [Pirk 67] - Add Slide Deck to the Website Documentation Explaining
>> the Mathematics of Pirk
>>
>> Argh! Walter you are driving me mad! :-)
>>
>> Thank you for putting up the slides, and I really want to grok this, but
>> I'm struggling to work through even the simplest of examples.
>> I need the kindergarten version :-(
>>
>> What am I doing wrong? I'm trying a very simple example. I'm going to
>> choose,
>> p = 3, q = 5 and a message m = 42
>>
>> Looking at page 11 on the math_deck.pdf line by line
>>
>> line 2:
>> N = 15.
>> I'm going to pick g = 240. I think it needs to be a multiple of N
>> that is greater than N*N, correct?
>>
>> line 3:
>> I'll pick zeta = 21. I think it needs to be greater than N.
>>
>> Line 4:
>> (240^42 x 21^15) mod 225 = 0
>>
>> That's suspicious.
>> ...and if I play with my free choices of m, g and zeta I always get zero.
>>
>> Help!
>>
>> I get the gist of the flow through the deck, but I want to work through
>> my own examples from top to bottom.
>>
>> Regards,
>> Tim
>>
>
>
