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?

Improve this question
$\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, 2021 at 20:19

1 Answer 1

Reset to default
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.

Improve this answer
$\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, 2021 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, 2021 at 20:31
  • $\begingroup$ Algebrae over GF(2) and over natural integers are two completely different topics! $\endgroup$
    – iBug
    May 8, 2021 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, 2021 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, 2021 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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