Not long ago there was a discussion on blinding which must be read if this is to make perfect sense, but it seems to me that it makes sufficient sense without it to be worth posting without rewriting to allow for the time lag - the context is that I disappeared in the midst of the discussion to go on holiday, and wrote this while I was away. I have only just retrieved it from my laptop. :-) Firstly, as I mentioned earlier, if you have a blinding function b for your oracle, f' [Editor's note: f is the easy function that f' can undo - most people think f' is hard, of course], then the unblinding function (u) is clearly going to be f'.b'.f. Now, since f' is known to be hard, u is only going to be any fun if it somehow renders itself non-hard. The obvious way for this to happen is for b' to commute with either f or f', in which case u becomes simply b' (see, it wasn't so silly to think the unblinding function was the inverse of the blinding function[1] :-). Conversely, if u is, in fact, b', then b' must commute with f, since b'=f'.b'.f => f.b'=b'.f. I'm not sure if this is useful, but it is true. Secondly, I've been thinking about the original question (blinding RSA cracking) - the only way I can see this working is if we have an oracle that is prepared to factor any number (that is, it needs to work with more than two prime factors) - i.e. f(p_1,...,p_n)=p_1.p_2...p_n and f'(p_1.p_2...p_n)=(p_1,...,p_n), and we have an x we want to crack blindly, we choose some extra factors b_1,...,b_k and multiply x by them. We submit the result to the oracle. When we get the answer, we discard the extra factors, and are left with the factors of x. In order for this to be any use, we have to use a sufficiently large number of factors that it is impractical for the oracle to determine which pair of factors (assuming that x actually only has two, as is usual) are the interesting ones. Since the oracle can factor public keys at will, the only way to achieve this is for the b_i to include a number of factors of other keys. But we don't know the factors of other keys[2], so we have to choose enough numbers that this happens at random. This means that k has to be exceedingly large, and the blinded number, correspondingly, will be k.log_2(x)/2 bits long, roughly (since the b_i must be around log_2(x)/2 bits long each to be convincing). IMO this makes RSA blinding possible but impractical, unless the oracle has access to alien technology that allows it to factor arbitrarily large numbers at little extra cost, but does not otherwise endow it with unusual computational powers. Note that the b_i must also be prime, so the cost of producing the blinded version of x is not insignificant. Cheers, Ben. [1] But only in the case where f' is hard, of course, which is why my earlier example was a bad one (square and square root, for those who, like me, are memory-impaired). [2] We could, of course, use the oracle to derive them, but the dangers of that are obvious. -- http://www.apache-ssl.org/ben.html Coming to ApacheCon Europe 2000? http://apachecon.com/
