9
$\begingroup$

Although it's hard for me to find a reference, it's my understanding that if you calculate $N = pq$ using $GF(2)$ polynomial multiplication rather than ordinary multiplication, it is easy to factor $N$ under this type of multiplication.

I might have the terminology wrong when I say "$GF(2)$ polynomial multiplication". I mean carryless or "XOR" multiplication done in base 2.

Is this true, and if so, does it mean that the security of RSA comes entirely from the addition carries that happen during ordinary multiplication?

$\endgroup$
1
  • 1
    $\begingroup$ The wording is strange. Indeed, factoring without carries (over GF(2)) is easy. Adding carries makes it hard. But it is the whole thing that is hard, not the carries themselves. $\endgroup$ – Fractalice May 7 at 20:19
12
$\begingroup$

might have the terminology wrong when I say "GF(2) polynomial multiplication"

You are thinking of multiplication in the ring of binary polynomials, that is polynomials with coefficients in the Galois Field with 2 elements. That set is noted $GF(2)[x]$. It's addition reduces to XOR of the coefficients of equal weight. It's multiplication is called "carryless multiplication" in computing. It supports an analog to Euclidean division, and modular arithmetic.

It's my understanding that if you calculate $N=pq$ using (this) multiplication rather than ordinary multiplication, it is easy to factor $N$.

Yes. There are efficient algorithms for factoring binary polynomials into irreducible polynomials (which are analogs to primes in the ring of binary polynomials).

Does it mean that the security of RSA comes entirely from the addition carries that happen during ordinary multiplication?

True, RSA is not secure if we remove the carries (in the additions within it's multiplication by the schoolbook algorithm). I can't agree with "security .. comes entirely". Analogy: a chain is insecure if one removes it's last link, yet it's security does not come entirely from that link.

$\endgroup$
5
  • 1
    $\begingroup$ Computing seems to give it at least three different names: "carryless multiplication" (x86), "polynomial multiplication" (ARM), "XOR multiplication" (SPARC). I'm a programmer by trade, so those were the names most natural to me, not the correct term. Sorry for the weird wording! $\endgroup$ – Myria May 7 at 20:26
  • $\begingroup$ @Myria: yes, I have often met "(binary) polynomial multiplication". If did now knew "XOR multiplication", but then I'm utterly unfamiliar with SPARC, and it's perfectly logical: binary polynomial multiplication can be obtained by changing binary addition to XOR in the usual binary multiplication algorithm. $\endgroup$ – fgrieu May 7 at 20:31
  • $\begingroup$ Algebrae over GF(2) and over natural integers are two completely different topics! $\endgroup$ – iBug May 8 at 4:05
  • 1
    $\begingroup$ I'd say the absence of carries makes quite some differences. For example, if we list a set of formulae for addition of two numbers, we'll see that the highest bit of the sum can depend on every input bit in $\mathbb Z$, while in GF(2)[x] it depends only on the same bits of input (reduction in complexity). Also, any element in GF(2)[x] is its own additive inverse, and the invalidation of Peano arithmetic, which gives multiplication a completely different nature since it's no longer "repetition of addition". $\endgroup$ – iBug May 8 at 6:27
  • 5
    $\begingroup$ I'm not to argue that your answer is wrong, but that the question is intrinsically flawed. Granted, arithmetic over $GF(2^n)$ is useful in other contexts, but when it comes to RSA, it's just like comparing apples to oranges. $\endgroup$ – iBug May 8 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.