diff options
Diffstat (limited to 'pipermail/pycrypto/2011q1/000411.html')
| -rw-r--r-- | pipermail/pycrypto/2011q1/000411.html | 101 |
1 files changed, 101 insertions, 0 deletions
diff --git a/pipermail/pycrypto/2011q1/000411.html b/pipermail/pycrypto/2011q1/000411.html new file mode 100644 index 0000000..b260e0a --- /dev/null +++ b/pipermail/pycrypto/2011q1/000411.html @@ -0,0 +1,101 @@ +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> +<HTML> + <HEAD> + <TITLE> [pycrypto] Why p<q in RSA code? + </TITLE> + <LINK REL="Index" HREF="index.html" > + <LINK REL="made" HREF="mailto:pycrypto%40lists.dlitz.net?Subject=%5Bpycrypto%5D%20Why%20p%3Cq%20in%20RSA%20code%3F&In-Reply-To=AANLkTinfHanB%2BxGjz6BLNYMRtH-mwZH54U172RHWHsQ%2B%40mail.gmail.com"> + <META NAME="robots" CONTENT="index,nofollow"> + <META http-equiv="Content-Type" content="text/html; charset=us-ascii"> + <LINK REL="Previous" HREF="000410.html"> + <LINK REL="Next" HREF="000412.html"> + </HEAD> + <BODY BGCOLOR="#ffffff"> + <H1>[pycrypto] Why p<q in RSA code?</H1> + <B>Paul Koning</B> + <A HREF="mailto:pycrypto%40lists.dlitz.net?Subject=%5Bpycrypto%5D%20Why%20p%3Cq%20in%20RSA%20code%3F&In-Reply-To=AANLkTinfHanB%2BxGjz6BLNYMRtH-mwZH54U172RHWHsQ%2B%40mail.gmail.com" + TITLE="[pycrypto] Why p<q in RSA code?">paul_koning at dell.com + </A><BR> + <I>Wed Jan 19 13:00:38 CST 2011</I> + <P><UL> + <LI>Previous message: <A HREF="000410.html">[pycrypto] Why p<q in RSA code? +</A></li> + <LI>Next message: <A HREF="000412.html">[pycrypto] Why p<q in RSA code? +</A></li> + <LI> <B>Messages sorted by:</B> + <a href="date.html#411">[ date ]</a> + <a href="thread.html#411">[ thread ]</a> + <a href="subject.html#411">[ subject ]</a> + <a href="author.html#411">[ author ]</a> + </LI> + </UL> + <HR> +<!--beginarticle--> +<PRE> +On Jan 19, 2011, at 1:29 PM, Legrandin wrote: + +>><i> I have noticed that - when generating an RSA key - a special check is +</I>>><i> made to ensure that p<q. +</I>>><i> +</I>>><i> That's interesting. This is what I found, which seems to suggest the exact +</I>>><i> opposite: +</I>>><i> +</I>>>>><i> +</I>>><i> To generate the primes p and q, generate a random number of [...] If p<q, swap +</I>>><i> p and q (this only matters if you intend using the CRT form of the private +</I>>><i> key) [...] +</I>>>>><i> +</I>>><i> +</I>>><i> Taken from <A HREF="http://www.di-mgt.com.au/rsa_alg.html">http://www.di-mgt.com.au/rsa_alg.html</A> +</I>>><i> +</I>>><i> That snippet suggests that p>q is desired if using the CRT form of the +</I>>><i> private key. And we seem to be doing the exact opposite, swapping p and q if +</I>>><i> p>q. +</I>><i> +</I>><i> Makes sense actually... +</I>><i> +</I>><i> The rsaDecrypt() routine in _fastmath.c (and possibly soon in +</I>><i> _slowmath.py ;-)) uses pInv = p^{-1} mod q, that is the u member in a +</I>><i> pycrypto RSA object. +</I>><i> In other words, the page you mention and pycrypto are the same if you +</I>><i> swap p and q. +</I>><i> +</I>><i> But still it does not explain *why* it must be p<q or p>q. +</I> +If you do modular arithmetic mod q on p -- which is what is being done here -- you'd want to start with p having a legal value mod q. Such a value is in the range 0..q-1, so that's why you'd have the check. + +p^-1 mod q will deliver a value in that range. You could argue that it should be valid even if p is outside the range -- effectively that means you're doing (p mod q)^-1 mod q. But I would expect your typical modular arithmetic package not to go through that extra work. + + paul + + +</PRE> + + + + + + + + + +<!--endarticle--> + <HR> + <P><UL> + <!--threads--> + <LI>Previous message: <A HREF="000410.html">[pycrypto] Why p<q in RSA code? +</A></li> + <LI>Next message: <A HREF="000412.html">[pycrypto] Why p<q in RSA code? +</A></li> + <LI> <B>Messages sorted by:</B> + <a href="date.html#411">[ date ]</a> + <a href="thread.html#411">[ thread ]</a> + <a href="subject.html#411">[ subject ]</a> + <a href="author.html#411">[ author ]</a> + </LI> + </UL> + +<hr> +<a href="http://lists.dlitz.net/cgi-bin/mailman/listinfo/pycrypto">More information about the pycrypto +mailing list</a><br> +</body></html> |