On 20/09/16 15:20, Walter Ray-Dulany wrote: >> Is this the same as I've seen this written elsewhere as double stroked Z >> subscript N? > > Most definitely. I write it the way that I do to for historical reasons > (mathematical and personal).
Ok, works well in ascii comments too. >> I assume that, practically, it is better to work with smaller factors to make >> the math operations faster (but not too small to compromise security) and >> chunk the message accordingly, rather than working with large messages. > > This is precisely what Pirk does. I guess my question is, does Pirk change the message chunk size depending upon the bit length of N? Seems that there is going to be some correlation there - if the message length is too small you are doing more calculations than necessary. Is this chunking the DataPartitioner's job? In which case I see the built-in partitioners are all going to 8-bit partitions. >> Whoa, why is g = 1 + N the standard Wideskies g? > > (1) It works (as I showed above), and (2) it turns out that all such g are > powers of (1+N). I'm not going to prove that, but it's true. > > Paillier's paper goes into detail about how the security of the system is > independent of the g one chooses. Since g is public, and since the security > of the system does not suffer for just choosing the same g every time, > Wideskies just says "screw it, we're going with 1+N". I'm curious, but I'll draw the line there and trust :-) >> How do you want to receive proposed changes to the PDF, if at all? I'm >> rephrasing >> your version a bit as I go, and quite happy to keep it separate so there is >> a simple version for those that don't "speak algebra". > > I've created another issue, PIRK-70, to add the LaTeX beamer doc from which > I generated the pdf, along with the relevant Pirk images. These docs will > live in the main branch (not the web branch) under contrib. This is in > addition to the changes I've made to the PDF to clarify the math language. > With the TeX there, anyone can edit the doc, if they so choose. Tim, you > could do that, or roll your own in whatever format you like. Cool, thanks. I'll keep working my way through it as I get a few mins. Please can you clarify, the doc for Wideskies algorithm (slide 16) says that zeta is chosen to be in (Z/N^2 Z)* -- but the code we have in Paillier.java[1] appears to be selecting for (Z/NZ)* [1] https://github.com/apache/incubator-pirk/blob/master/src/main/java/org/apache/pirk/encryption/Paillier.java#L257 Regards, Tim > What do you think? > > Walter > > On Tue, Sep 20, 2016 at 8:33 AM, Tim Ellison <t.p.elli...@gmail.com> wrote: > >> On 19/09/16 18:36, Walter Ray-Dulany wrote: >>> 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 appreciate your patience Walter. I'm sure this "just makes sense" to >> you, but my brain is hurting trying to keep up :-) >> >>> ************************** >>> >>>> 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 >> >> Ah, so understanding the notation was confusing me, which is not going >> to help! Is this the same as I've seen this written elsewhere as double >> stroked Z subscript 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 >> >> Interesting. That means that the size of message I can encode directly >> using this scheme is related to the bit length of my RSA factors. >> >> I assume that, practically, it is better to work with smaller factors to >> make the math operations faster (but not too small to compromise >> security) and chunk the message accordingly, rather than working with >> large messages. >> >>> ************************** >>> >>>> 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. >> >> Ok, got that. >> >>> 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. >> >> Whoa, why is g = 1 + N the standard Wideskies g? >> >> I was following what you said, and thinking, ok I've got to pick a value >> for g that >> (i) does not have p or q as a factor, >> (ii) 0 <= g < N*N, and >> (iii) has multiplicative order that's a non-zero multiple of N >> >> this is going to take some finding ... then you simply say N + 1 ?! >> >> I would go through with a different g, but it may take me a while to >> sift through and find one without knowing the trick :-) >> >>> ************************** >>> >>>> 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. >> >> So apart from the fact that I picked all the numbers incorrectly I was >> on the right lines :-) D'oh. >> >> >>> ************************** >>> >>> 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. >> >> I'll get to decryption in a moment. I want to have this encrypt sorted >> first. >> >>> ************************** >>> >>> 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, >> >> Thanks for the offer. I'm happy to demonstrate my ignorance on the >> list, and work towards a description that hopefully is useful to anyone >> else coming from the same direction. >> >> How do you want to receive proposed changes to the PDF, if at all? I'm >> rephrasing your version a bit as I go, and quite happy to keep it >> separate so there is a simple version for those that don't "speak algebra". >> >> Regards, >> Tim >> >> >>> 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 >>>> >>> >> >
