Re: Averaging RSA ciphertexts

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
.

Relevant Pages

  • Re: Averaging RSA ciphertexts
    ... You are given a valid RSA public key. ... Select the ciphertexts that match the bits of p in more than or equal to 1/2 ... This phrase is NONSENSE. ... Use the ciphertexts that satisfy the filter rule. ...
    (sci.crypt)
  • Averaging RSA ciphertexts
    ... You are given a valid RSA public key. ... Select the ciphertexts that match the bits of p in more than or equal to 1/2 ... Use the ciphertexts that satisfy the filter rule. ... The output of the recoding step matches p, ...
    (sci.crypt)
  • Re: Averaging RSA ciphertexts - inferences
    ... RSA is irrelevant except as a source of random bits. ... Then generalize to any bit pattern p. ... the filtered subset of ciphertexts is likely true, for RSA and for a random ... different from the distribution of noise generated by the RSA cipher. ...
    (sci.crypt)
  • Reconstructing p from RSA outputs?
    ... RSA is irrelevant except as a source of random bits. ... Then generalize to any bit pattern p. ... the filtered subset of ciphertexts is likely true, for RSA and for a random ... different from the distribution of noise generated by the RSA cipher. ...
    (sci.crypt)