blob: 23e44a545dae443a84acd4b034fc83e0dfe1cb0e (
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
|
<!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=CB45E8BE-E31D-4543-8841-E202E16EA288%40dell.com">
<META NAME="robots" CONTENT="index,nofollow">
<META http-equiv="Content-Type" content="text/html; charset=us-ascii">
<LINK REL="Previous" HREF="000411.html">
<LINK REL="Next" HREF="000418.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=CB45E8BE-E31D-4543-8841-E202E16EA288%40dell.com"
TITLE="[pycrypto] Why p<q in RSA code?">gooksankoo at hoiptorrow.mailexpire.com
</A><BR>
<I>Wed Jan 19 14:06:05 CST 2011</I>
<P><UL>
<LI>Previous message: <A HREF="000411.html">[pycrypto] Why p<q in RSA code?
</A></li>
<LI>Next message: <A HREF="000418.html">[pycrypto] PKCS#1 v1.5 and PSS
</A></li>
<LI> <B>Messages sorted by:</B>
<a href="date.html#412">[ date ]</a>
<a href="thread.html#412">[ thread ]</a>
<a href="subject.html#412">[ subject ]</a>
<a href="author.html#412">[ 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> 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.
</I>><i>
</I>><i> 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.
</I>><i>
</I>><i> paul
</I>
I see, thanks.
Both Crypto.Util.number.inverse() and mpz_invert() work correctly if the
number to invert is larger than the modulus though, therefore I
understand that the check is actually redundant.
Note that I am not advocating to remove the check (if it's not broken
don't fix it). The problem I was considering is that a private key imported
as PEM could have p>q, because the standard does not prescribe any ordering.
Given that, should p and q be swapped (p to becomes q, q to become p) when p>q
or not?
I believe it is not necessary, but I had no hard proof that a flaw was
not lurking by doing that.
I would adjust the comment "# p shall be smaller than q (for calc of u)"
though because it is simply not right, along with the test cases that verify
that p<q....
</PRE>
<!--endarticle-->
<HR>
<P><UL>
<!--threads-->
<LI>Previous message: <A HREF="000411.html">[pycrypto] Why p<q in RSA code?
</A></li>
<LI>Next message: <A HREF="000418.html">[pycrypto] PKCS#1 v1.5 and PSS
</A></li>
<LI> <B>Messages sorted by:</B>
<a href="date.html#412">[ date ]</a>
<a href="thread.html#412">[ thread ]</a>
<a href="subject.html#412">[ subject ]</a>
<a href="author.html#412">[ 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>
|
