Anyone Good with Cryptography?

So I’m writing an essay about the Paillier cryptosystem, and have been having some troubles figuring it out. I’ve tried asking questions about it on 4 cryptography/math specific forums, but no one has been able (or just not been bothered…) to help. There are some pretty smart guys on here so I figured there might be a chance that there’d be someone on here that could help me. I’ll do a worked example and point out where I’m having problems:

Key Generation
n=pq
p= 53, q=61
n = 3233 = 53*61

(lambda) = lcm (p-1,q-1)
(lambda) = lcm(52,60) = 780

g = y^n mod n^2
g = 20^3233 mod 3233^2 = 9283294
This is the first step that I’m a bit confused about. From what I understand you choose a random y ingeger and calculate g from that, correct?

Encryption
Message= 13
r = 17
ciphertext = g^m * r^n mod n^2
Ciphertext = 9283294^13 * 17^3233 mod 3233^2 = 4267322

Decryption
m = ((L(c^(lambda) mod n^2)/(L(g^(lambda) mod n^2)) mod n
where L = (u-1)/n
I’m not completely sure what u is, but from what I gather it’s a “dummy variable” meaning that you use whatever is in front of it as the variable (without the modulo)

m = (((c^lambda -1)/n)(c^lambda mod n^2)/((g^lambda -1)/n)(g^lambda mod n^2)) mod n
m= (((4267322^780 - 1)/3233)(4267322^780 mod 3233^2)/((9283294^780 - 1)/3233)(9283294^780 mod 3233^2))mod 3233

When I enter this into maple, I get the following message “Error, the modular inverse does not exist”. I’ve managed to not get an error message before, but message received has not been the same as was sent. Can anyone point out where I’m going wrong here?
Thanks

All I learned was that Mister X is omnipotent.


.

[quote]DOHCrazy wrote:
.[/quote]

That’s all I got from reading that to.

I’m not familiar with this particular cryptosystem but according to this:

You select a random g, not y during key generation. I’m not sure what the notation they’re using implies but it has to be a g such that “n divides the order of g”.

When it says the modular inverse does not exist I’m assuming that means that you’ve selected an invalid g, such that when trying to verify the existence of the modular inverse it doesn’t exist. eg. the g you’ve chosen produces an inverse of infinity or 0 or something to that extent.

If I’m bored later I might read this a little more thoroughly and see if I can figure it out, maybe someone with knowledge of this particular system can chime in before then though.

[quote]JLu wrote:
I’m not familiar with this particular cryptosystem but according to this:

You select a random g, not y during key generation. I’m not sure what the notation they’re using implies but it has to be a g such that “n divides the order of g”.

When it says the modular inverse does not exist I’m assuming that means that you’ve selected an invalid g, such that when trying to verify the existence of the modular inverse it doesn’t exist. eg. the g you’ve chosen produces an inverse of infinity or 0 or something to that extent.

If I’m bored later I might read this a little more thoroughly and see if I can figure it out, maybe someone with knowledge of this particular system can chime in before then though.[/quote]

Thanks, turns out that my problem is with the value of “r” after a quick google search about this error. The original paper stimply states “choose a random r<n”. Turns out that r must have a “modular inverse of mod n”. I’m having trouble figuring out how the modular inverse applies to this as I’m familiar with the extended euclidian algorithm, however only in the ax + by = 1 form, where a and b are known (this would be r + n*y =1, which would just make r = n+1 and y = -1 and “n” is known). Do you have any knowledge about how this would work, seeing as modular inverses are also used elsewhere in cryptography/number theory, and not necessarily specific to this system. Also if it’s any help this ( http://upload.wikimedia.org/math/2/f/7/2f75a990ffd01adcf1ce6e894a832f85.png ) is another method of stating what “r” should be. Personally, I don’t know what that means, but I guess if you have a background in number theory/cryptography this could mean something to you?
Thanks

[quote]Scorzerci wrote:
JLu wrote:
I’m not familiar with this particular cryptosystem but according to this:

You select a random g, not y during key generation. I’m not sure what the notation they’re using implies but it has to be a g such that “n divides the order of g”.

When it says the modular inverse does not exist I’m assuming that means that you’ve selected an invalid g, such that when trying to verify the existence of the modular inverse it doesn’t exist. eg. the g you’ve chosen produces an inverse of infinity or 0 or something to that extent.

If I’m bored later I might read this a little more thoroughly and see if I can figure it out, maybe someone with knowledge of this particular system can chime in before then though.

Thanks, turns out that my problem is with the value of “r” after a quick google search about this error. The original paper stimply states “choose a random r<n”. Turns out that r must have a “modular inverse of mod n”. I’m having trouble figuring out how the modular inverse applies to this as I’m familiar with the extended euclidian algorithm, however only in the ax + by = 1 form, where a and b are known (this would be r + n*y =1, which would just make r = n+1 and y = -1 and “n” is known). Do you have any knowledge about how this would work, seeing as modular inverses are also used elsewhere in cryptography/number theory, and not necessarily specific to this system. Also if it’s any help this ( http://upload.wikimedia.org/math/2/f/7/2f75a990ffd01adcf1ce6e894a832f85.png ) is another method of stating what “r” should be. Personally, I don’t know what that means, but I guess if you have a background in number theory/cryptography this could mean something to you?
Thanks[/quote]

the symbols in the link, http://upload.wikimedia.org/math/2/f/7/2f75a990ffd01adcf1ce6e894a832f85.png , mean that r is a number from the set {1, 2, 3, … , n-1}, ie, r is a nonzero positive integer less then n.

I’m sure I have enough background in number theory to help you (plus I’m vaguely familiar with public key systems, certainly not this in particular though), but I’m not sure I’ll have time. If I have time tonight or tomorrow I’ll give this a go and either post back here or pm you.

Feel free to PM me, I looked over the wiki and know what’s going on. For now here’s some quick answers, hopefully they help.

[quote]Scorzerci wrote:
The original paper stimply states “choose a random r<n”. Turns out that r must have a “modular inverse of mod n”.
[/quote]

I’m not sure how much you know about modular arithematic, but when it says that r must have an inverse mod n, what it means in simple terms is that if r is less than n, then there must be another natural number k also less than n such that rk = 1 (mod n), or in other words such that rk - 1 = qn , for some other integer q (even more simply, the number rk - 1 must divide n).

Hopefully that helps you pick the right r. As for why r must have that inverse, that would take a bit of number theory to explain.

While the euclidian algorithm has some applications in all this, see my explanation above about what it means for r to have an inverse mod n.

Again, just ask anything else you want.

[quote]stokedporcupine8 wrote:
Feel free to PM me, I looked over the wiki and know what’s going on. For now here’s some quick answers, hopefully they help.

Scorzerci wrote:
The original paper stimply states “choose a random r<n”. Turns out that r must have a “modular inverse of mod n”.

I’m not sure how much you know about modular arithematic, but when it says that r must have an inverse mod n, what it means in simple terms is that if r is less than n, then there must be another natural number k also less than n such that rk = 1 (mod n), or in other words such that rk - 1 = qn , for some other integer q (even more simply, the number rk - 1 must divide n).

Hopefully that helps you pick the right r. As for why r must have that inverse, that would take a bit of number theory to explain.

I’m having trouble figuring out how the modular inverse applies to this as I’m familiar with the extended euclidian algorithm, however only in the ax + by = 1 form, where a and b are known (this would be r + n*y =1, which would just make r = n+1 and y = -1 and “n” is known). Do you have any knowledge about how this would work, seeing as modular inverses are also used elsewhere in cryptography/number theory, and not necessarily specific to this system.

While the euclidian algorithm has some applications in all this, see my explanation above about what it means for r to have an inverse mod n.

Again, just ask anything else you want.

[/quote]

you’re going to be getting a lot of PM’s from me when school starts.

I want to go to school so bad right now

[quote]LiveFromThe781 wrote:
stokedporcupine8 wrote:
Feel free to PM me, I looked over the wiki and know what’s going on. For now here’s some quick answers, hopefully they help.

Scorzerci wrote:
The original paper stimply states “choose a random r<n”. Turns out that r must have a “modular inverse of mod n”.

I’m not sure how much you know about modular arithematic, but when it says that r must have an inverse mod n, what it means in simple terms is that if r is less than n, then there must be another natural number k also less than n such that rk = 1 (mod n), or in other words such that rk - 1 = qn , for some other integer q (even more simply, the number rk - 1 must divide n).

Hopefully that helps you pick the right r. As for why r must have that inverse, that would take a bit of number theory to explain.

I’m having trouble figuring out how the modular inverse applies to this as I’m familiar with the extended euclidian algorithm, however only in the ax + by = 1 form, where a and b are known (this would be r + n*y =1, which would just make r = n+1 and y = -1 and “n” is known). Do you have any knowledge about how this would work, seeing as modular inverses are also used elsewhere in cryptography/number theory, and not necessarily specific to this system.

While the euclidian algorithm has some applications in all this, see my explanation above about what it means for r to have an inverse mod n.

Again, just ask anything else you want.

you’re going to be getting a lot of PM’s from me when school starts.
[/quote]

ah, I probably won’t be around the boards much in another week or so, but if I get a notice about a PM I’ll check it. I like little problems like this, so if I have time I’ll gladly help.

[quote]stokedporcupine8 wrote:
Feel free to PM me, I looked over the wiki and know what’s going on. For now here’s some quick answers, hopefully they help.

Scorzerci wrote:
The original paper stimply states “choose a random r<n”. Turns out that r must have a “modular inverse of mod n”.

I’m not sure how much you know about modular arithematic, but when it says that r must have an inverse mod n, what it means in simple terms is that if r is less than n, then there must be another natural number k also less than n such that rk = 1 (mod n), or in other words such that rk - 1 = qn , for some other integer q (even more simply, the number rk - 1 must divide n).

Hopefully that helps you pick the right r. As for why r must have that inverse, that would take a bit of number theory to explain.

I’m having trouble figuring out how the modular inverse applies to this as I’m familiar with the extended euclidian algorithm, however only in the ax + by = 1 form, where a and b are known (this would be r + n*y =1, which would just make r = n+1 and y = -1 and “n” is known). Do you have any knowledge about how this would work, seeing as modular inverses are also used elsewhere in cryptography/number theory, and not necessarily specific to this system.

While the euclidian algorithm has some applications in all this, see my explanation above about what it means for r to have an inverse mod n.

Again, just ask anything else you want.

[/quote]

Thanks for the help, I sent a PM to Stokedporcupine8, but I’ll post my question here as well in case anyone is able to help in the meantime:
There’s one more thing that I’m a bit confused about. You said that rk - 1 is divisible by n, which can be rearranged to rk - qn = 1. To find “r”, would I have to simply try out a value and see if there are any integers k and q which satisfy this relationship, or is there any way that an “r” can be found which works with this relationship which does not involve trial and error?
Thanks

[quote]Scorzerci wrote:
stokedporcupine8 wrote:
Feel free to PM me, I looked over the wiki and know what’s going on. For now here’s some quick answers, hopefully they help.

Scorzerci wrote:
The original paper stimply states “choose a random r<n”. Turns out that r must have a “modular inverse of mod n”.

I’m not sure how much you know about modular arithematic, but when it says that r must have an inverse mod n, what it means in simple terms is that if r is less than n, then there must be another natural number k also less than n such that rk = 1 (mod n), or in other words such that rk - 1 = qn , for some other integer q (even more simply, the number rk - 1 must divide n).

Hopefully that helps you pick the right r. As for why r must have that inverse, that would take a bit of number theory to explain.

I’m having trouble figuring out how the modular inverse applies to this as I’m familiar with the extended euclidian algorithm, however only in the ax + by = 1 form, where a and b are known (this would be r + n*y =1, which would just make r = n+1 and y = -1 and “n” is known). Do you have any knowledge about how this would work, seeing as modular inverses are also used elsewhere in cryptography/number theory, and not necessarily specific to this system.

While the euclidian algorithm has some applications in all this, see my explanation above about what it means for r to have an inverse mod n.

Again, just ask anything else you want.

Thanks for the help, I sent a PM to Stokedporcupine8, but I’ll post my question here as well in case anyone is able to help in the meantime:
There’s one more thing that I’m a bit confused about. You said that rk - 1 is divisible by n, which can be rearranged to rk - qn = 1. To find “r”, would I have to simply try out a value and see if there are any integers k and q which satisfy this relationship, or is there any way that an “r” can be found which works with this relationship which does not involve trial and error?
Thanks[/quote]

If you let r be prime it should always have an inverse, unless your mod is some power of that prime. For example, if n is 12 then let r be 5. Then 5 is its own inverse, since 55=25=1 mod 12. In other words let k=5 and q=2 and rk - 1 = qn gives us 55 - 1 = 2*12, which is of course true.

As for a general method of picking k and q’s in order to prove that some number r has an inverse mod n, I don’t believe any exists. If you pick prime numbers though, they should always exist so long as n isn’t a power of that prime.

I PM’d Scorzerci a fully worked example of an encryption and decryption using this system. If anyone else wants to see it, I’ll send it to them.