Re:Florida House of Representatives approves bill to ban soc...
by tzs on Monday January 29, 2024 @03:01PM
(#39181650)
An example of the kind of token transformation I'm thinking of follows.
Assume RSA signatures from the site that looks at your ID having public key (e,m) where e is the exponent and m is the modules, and private key d. The signature s of a blob of data, b, that you give them is b^d mod m.
To verify the signature one computes s^e mod m and checks if that matches b.
Here's the transformation. You generate a random r from 1 to m-1 such that r is relatively prime to m. Compute r' such that r r' = 1 mod m.
Instead of sending b to be signed, send b r^e mod m.
The signature s of b r^e is (b r^e)^d mod m = b^d r mod m.
You take that signature and multiply by r'. That gives you b^d mod m. Note that this is the signature you would have gotten had you sent them b to sign instead of b r^e.
Net result: you've obtained the signature of b, but the signing site never saw b. They just saw b r^e mod m.
That gives them no useful information about b, due to r being a random number that you picked (assuming you used a good random number generator!).
For any possible b, as long as it is relatively prime to m, there is some r that would result in b r^e having the same signature as your b, so the signing site has no way to tell which is really yours.
b is unlikely to not be relatively prime to m. If m is the product of two large primes, as is common, b is relatively prime to it unless one of those primes divides b. We can ensure that b is relatively prime to m by simply limiting b to be smaller than either of the prime factors of m. Since those factors are likely to each be over a thousand bits this is not hard. In practice b would probably be something like a random 128 bits.
Assume RSA signatures from the site that looks at your ID having public key (e,m) where e is the exponent and m is the modules, and private key d. The signature s of a blob of data, b, that you give them is b^d mod m.
To verify the signature one computes s^e mod m and checks if that matches b.
Here's the transformation. You generate a random r from 1 to m-1 such that r is relatively prime to m. Compute r' such that r r' = 1 mod m.
Instead of sending b to be signed, send b r^e mod m.
The signature s of b r^e is (b r^e)^d mod m = b^d r mod m.
You take that signature and multiply by r'. That gives you b^d mod m. Note that this is the signature you would have gotten had you sent them b to sign instead of b r^e.
Net result: you've obtained the signature of b, but the signing site never saw b. They just saw b r^e mod m.
That gives them no useful information about b, due to r being a random number that you picked (assuming you used a good random number generator!).
For any possible b, as long as it is relatively prime to m, there is some r that would result in b r^e having the same signature as your b, so the signing site has no way to tell which is really yours.
b is unlikely to not be relatively prime to m. If m is the product of two large primes, as is common, b is relatively prime to it unless one of those primes divides b. We can ensure that b is relatively prime to m by simply limiting b to be smaller than either of the prime factors of m. Since those factors are likely to each be over a thousand bits this is not hard. In practice b would probably be something like a random 128 bits.