Reconstructing p from RSA outputs?
 From: "kentucky" <pam@xxxxxxxxxxxx>
 Date: Thu, 22 Jun 2006 01:24:29 +0930
I assume the "limit" is as the number of messages increases without
bound.
Yes
6. Question:
Why is this so?
This would be true for any bit pattern p and source of random
ciphertexts. RSA is irrelevant except as a source of random bits. Try to
prove it for p=all zeros. Then generalize to any bit pattern p.
I do not know (at this time) how to proceed with a proof.
However, I can demonstrate that it is true when p=all zeros.
It seems, that you suspect that the consequence (reconstruction of p) from
the filtered subset of ciphertexts is likely true, for RSA and for a random
bit source generally?
Question: What do you think of the following inferences:
1. There exists a subset of RSA ciphertexts created with p, that always
approximate p, under averaging, as previously described?
2. There exists a nonexponential procedure by which the required subset of
ciphertexts from which p can be reconstructed, can be found without any
prior knowledge of p, q, or n?
3. As a first thought, the procedure may exploit the fact that the
distribution from which p is selected (RSA defined primes) is statistically
different from the distribution of noise generated by the RSA cipher. This
implies that the those ciphertexts that carry a strong image of the
contaminant digital signal p may be distinguished from those ciphertexts
that carry only a weak image of p. Ciphertexts with a strong image of p are
those that satisfy the aforementioned filter and have a significant
similarity to the statistical properties of the set of RSA defined primes.
The
difference in the statistical properties of the distributions (pprimes and
RSA output)
may be used to identify the ciphertexts that carry the strongest evidence of
having been
selected from the general population of RSA primes?
4. If the two distributions are very close then the chances of a successful
run of the procedure will be low otherwise the ciphertexts carrying p
can be distinguished and used to reconstuct p (as demonstrated below).
4.1 Question: How close are the properties of two distributions.
That is pprimes and RSA output?
4.2 Question: Was there an RSA requirement that p should be chosen from the
same distribution as one that we would characterise as having come from a
"random source"?
"Mike Amling" <nospam@xxxxxxxxxx> wrote in message
news:F_Vlg.256$7i.63@xxxxxxxxxxxxxxxxxxxx
kentucky wrote:
1. Scenario:
You are given a valid RSA public key.
The public key is used to encrypt a number of arbitrary plaintexts in the
standard manner.
Ciphertexts are the result.
Assume (for now) that you know the value of p. "p" is the bit pattern
used in n = p*q.
2. Filter Rule:
Select the ciphertexts that match the bits of p in more than or equal to
1/2 the bits of p.
The comparison in done against the lower 1/2 of the ciphertexts.
3. Summing the Filtered subset:
Use the ciphertexts that satisfy the filter rule.
Discard (for now) the rest as too noisy digital versions of p.
Lay the ciphertexts on upon the other.
Sum the bits in the lower 1/2 of the ciphertexts.
Divide each sum by the number of ciphertexts that satisfied the filter
rule.
The results are real valued and have 0 <= magnitude <= 1, and oscillate
closely about 1/2.
4. Recoding the real values:
Recode the real values from the previous step as follows:
If the real value is < 1/2, output a 0.
If the real value is >= 1/2, output a 1.
5. Observation:
The output of the recoding step matches p, in the limit.
I assume the "limit" is as the number of messages increases without
bound.
6. Question:
Why is this so?
This would be true for any bit pattern p and source of random
ciphertexts. RSA is irrelevant except as a source of random bits. Try to
prove it for p=all zeros. Then generalize to any bit pattern p.
Mike Amling
.
 Prev by Date: Entropy of pprimes: Is this what is expected?
 Next by Date: Re: Entropy of pprimes: Is this what is expected?
 Previous by thread: Entropy of pprimes: Is this what is expected?
 Next by thread: Extremely Fast Verification of PublicKey System
 Index(es):
Relevant Pages
