Re: some questions about permutation

David Wagner wrote:
laicko wrote:
David Wagner wrote:
Two independently chosen RSA trapdoor permutations won't commute.
I have said in former statement that two permutations have the same
range and domain. Or I'm wrong with the concept ---two indepentdently
choosen RSA permutations could have the same range and domain?

As you feared, two independently chosen RSA trapdoor permutations won't
have the same range and domain. Choosing a random RSA trapdoor permutation
means choosing random (e,n). The domain and range is (Z/nZ)^*, which is
different for each trapdoor permutation. Choose two different trapdoor
permutations will give you two different values of (e,n).

Well, with the modification that Rivest, Shamir and Adleman proposed in their original paper (or "report", DG), it's easy to get RSA domains and ranges to coincide. Choose p and q such that N=pq is slightly above r, the upper limit of the desired range, typically a power of 2. Then to get Range=Domain=0..r-1, instead of just raising m**e mod N, iterate raising to the eth power until the result is <=r.
RSAtransform(m, e_or_d, N) {
x=m**e_or_d mod N;
while (x>=r) {
x=x**e_or_d mod N;
}
return x;
}

The revised algorithm is still a trapdoor permutation, reversible by substituting e for d or vice versa. I would think two such RSA keypairs would be highly unlikely to commute, although offhand I don't see a proof that finding an (e', d', N') that commuted with an (e, d, N) whose d is unknown would allow calculating m**d mod N for arbitrary m.

--Mike Amling
.

Relevant Pages

  • Re: some questions about permutation
    ... small permutations, say on the numbers. ... And I know that's true for RSA with any instances. ... subgroup with the order unknown. ...
    (sci.crypt)
  • Re: Public-Key Key Exchange based on Parameterized Permutations
    ... composite commutative parameterized permutations. ... in parallel using virtual commutative involution pairs. ... Non-overlapping multiple bit fields for which parameters are the amount ... >> You cannot assume that any or all of the Pxi commute with Pbi. ...
    (sci.crypt)
  • Re: some questions about permutation
    ... and anything related to encrption. ... DES in net but it is not clear on how the permutation is done and which ... I have said in former statement that two permutations have the same ... Choosing a random RSA trapdoor permutation ...
    (sci.crypt)
  • Re: groups
    ... What permutations of 4 letters commute with EVERY ... This in turn means that if you write sigma ...
    (sci.math)
  • Re: some questions about permutation
    ... I have said in former statement that two permutations have the same ... two independently chosen RSA trapdoor permutations won't ... Choosing a random RSA trapdoor permutation ...
    (sci.crypt)