Hey Walter / Tim, I just wanted to add I had some trouble similar to Tim's when trying to understand the Wideskies paper. As a person without a background in group theory/theoretical math trying to get my head around this stuff, it was very difficult for me to even find with Google what the notations (Z/NZ) and (Z/N^2 Z)^x (also called (Z/N^2 Z)* in the Wideskies/Paillier papers) meant. Since these concepts are so central to how the algorithm works, I think it would be really helpful if we had a footnote the first time those are introduced defining that notation with links to a more in-depth explanation, or at least a phrase that can be Googled to reliably find it.
Thanks, -Ryan Carr On Mon, Sep 19, 2016 at 1:50 PM Walter Ray-Dulany <raydul...@apache.org> wrote: > 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 > >> > > > > >