Loading...
Please wait, while we are loading the content...
Similar Documents
Cryptography ( Winter 2006 ) Lecture 13 : Public Key Encryption Schemes 15 February 2006
| Content Provider | Semantic Scholar |
|---|---|
| Author | Squaring, Blum |
| Copyright Year | 2006 |
| Abstract | Recall the collection of functions {BlumN : QRN → QRN} were BlumN = x mod N for so-called Blum integers N that are products of two distinct primes congruent to 3 mod 4 are candidate one-way functions. As we mentioned earlier, inverting for algorithms for BlumN yield algorithms for factoring N . We now show that for N = pq, p 6= q prime, p, q ≡ 3 (mod 4), the pair (p, q) of factors of N forms trapdoor for BlumN . Consider the non-zero integers mod p, Zp. Recall that Zp is cyclic, equalling {1, g, g, . . . , gp−2} for some g ∈ Zp. QRp consists of the set of even powers of g, g for some integer k. Therefore if h ∈ QRp then h(p−1)/2 = (g2k)(p−1)/2 ≡ 1 (mod p). If h = q then h(p−1)/2 = (g2k+1)(p−1)/2 = g(p−1)/2 ≡ −1 (mod p). Now suppose that p = 4m + 3; in this case in particular (−1)(p−1)/2 = (−1) = −1 and thus −1 is not a quadratic residue. Moreover, suppose now that a ∈ QRp. Then a(p−1)/2 ≡ 1 (mod p). Thus a ≡ 1 (mod p) and thus a ≡ a (mod p). In particular, this means that if bp = a m+1 mod p = a mod p then bp ≡ (a) ≡ a (mod p). Thus bp is a square root of a modulo p. By similar computation define bq = a (mod q). Then bq ≡ a (mod q). We now have square roots ±bp and ±bq of a modulo p and q respectively. Since −1 is not in QRp, only one of bp or −bp will be in QRp; similarly, only one of bq or −bq will be in QRq. Assume without loss of generality that the elements of QRp and QRq are bp and bq respectively. We now use Chinese remaindering to find a b ∈ QRN such that b ≡ a (mod N). |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://courses.cs.washington.edu/courses/cse599b/06wi/lecture13.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
