blob: 86ffcf2ab0b608fa78283175c49c24b1997e6c49 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
<!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=4D3704BF.6000808%40gmx.li">
<META NAME="robots" CONTENT="index,nofollow">
<META http-equiv="Content-Type" content="text/html; charset=us-ascii">
<LINK REL="Previous" HREF="000409.html">
<LINK REL="Next" HREF="000411.html">
</HEAD>
<BODY BGCOLOR="#ffffff">
<H1>[pycrypto] Why p<q in RSA code?</H1>
<B>Legrandin</B>
<A HREF="mailto:pycrypto%40lists.dlitz.net?Subject=%5Bpycrypto%5D%20Why%20p%3Cq%20in%20RSA%20code%3F&In-Reply-To=4D3704BF.6000808%40gmx.li"
TITLE="[pycrypto] Why p<q in RSA code?">gooksankoo at hoiptorrow.mailexpire.com
</A><BR>
<I>Wed Jan 19 12:29:24 CST 2011</I>
<P><UL>
<LI>Previous message: <A HREF="000409.html">[pycrypto] Why p<q in RSA code?
</A></li>
<LI>Next message: <A HREF="000411.html">[pycrypto] Why p<q in RSA code?
</A></li>
<LI> <B>Messages sorted by:</B>
<a href="date.html#410">[ date ]</a>
<a href="thread.html#410">[ thread ]</a>
<a href="subject.html#410">[ subject ]</a>
<a href="author.html#410">[ author ]</a>
</LI>
</UL>
<HR>
<!--beginarticle-->
<PRE>><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>
Makes sense actually...
The rsaDecrypt() routine in _fastmath.c (and possibly soon in
_slowmath.py ;-)) uses pInv = p^{-1} mod q, that is the u member in a
pycrypto RSA object.
In other words, the page you mention and pycrypto are the same if you
swap p and q.
But still it does not explain *why* it must be p<q or p>q.
PKCS#1 states that qInv must be less than p (and in pycrypto it would
be pInv to be less than q), but that's fine. All other papers on the
net (including Handbook of Applied Cryptography) don't set any
constraint on the relative size of p with respect to q...
I have tried to remove the p/q swappings in pycrypto and the trivial
test cases that fail if p>q, and everything passes. Not that it proves
much (there may be probabilistic failures), but still...
On a separate note, LOL for the Nov 15 2010 comment in the page you
sent the link of.... :-D
</PRE>
<!--endarticle-->
<HR>
<P><UL>
<!--threads-->
<LI>Previous message: <A HREF="000409.html">[pycrypto] Why p<q in RSA code?
</A></li>
<LI>Next message: <A HREF="000411.html">[pycrypto] Why p<q in RSA code?
</A></li>
<LI> <B>Messages sorted by:</B>
<a href="date.html#410">[ date ]</a>
<a href="thread.html#410">[ thread ]</a>
<a href="subject.html#410">[ subject ]</a>
<a href="author.html#410">[ 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>
|
