# Removing 1 modular exponentiation

James Muir jamuir at scs.carleton.ca
Mon Feb 19 21:40:24 UTC 2007

```Mike Perry wrote:
>
>> Hello!
>> Tor currently uses RSA encrypted DH exchanges. This requires that the
>> server and client both make 3 exponentiations: Two for DH, One for RSA.
>> But we can reduce this significantly. I've already presented this
>> before, but now I think I can justify security. Sanity checks are assumed.
>>
>> Cryptographic Personae: Anonymous Alice and Ricky the Onion Router.
>> Protocol Paramaters: A group with a "generator" g that takes on m
>> values. DDH is hard in the group. I put generator in quotes because a
>> lot of the time it's not a mathematical generator. The group is written
>> multiplicatively.
>> Setup: Ricky picks a random positive integer k less then m. Let y be
>> Ricky's public key. Then y=g^k.
>> Protocol round 1: Alice picks a random positive integer a. Let f=y^a.
>> Alice sends f to Ricky.
>> Protocol round 2: Ricky picks a random positive integer b. Let h=g^b.
>> Key calculation: Ricky computes the key as f^(b/k) where
>> (g^(k))^(1/k)=g. Alice computes the key as h^a. Note that both Ricky and
>> Alice perform 2 group exponentiations.
>
> Well, one immediate problem is that b/k has to be an integer.. So b=rk
> for some random r and b is thus not completely random.. To clarify the
> effects of this, you should rewrite your protocol as follows from
> Round 2 on:

that's not really a problem.  all computations are done in the group
ZZ_p. 1/k really means the inverse of k modulo the order of g in ZZ_p.
So b/k does not have to be an integer.

putting the security of the scheme aside, one question that comes to
mind is how Alice (the OP) is going to get an authentic copy of Ricky's
DH public key, y.  One way to do this is to include it in the router
descriptors.  But then we have to ask if it's worth adding a new public
key for each OR to the Tor PKI to just save one exponentiation during
session key agreement.

-James

```