Relevant code (from <a href="https://gitlab.com/swisspost-evoting/crypto-primitives/crypto-primitives/-/raw/master/Crypto-Primitives-Specification.pdf" rel="nofollow">https://gitlab.com/swisspost-evoting/crypto-primitives/crypt...</a>):<p><pre><code> 𝑠𝑝 ← 8530092
▷ I.e. 0b100000100010100010101100: for all primes 𝑝 ≤ 23,
TestBit(𝑠𝑝, 𝑝) = true
if 𝑛 ≤ 23 then
▷ Quick check for small values, simpler and faster
than testing equality on each option
return TestBit(𝑠𝑝, 𝑛)
end if
if ¬TestBit(𝑛, 0) then return ⊥
▷ I.e. 𝑛 is even and, as per line 2, 𝑛 > 2 thus composite
end if
</code></pre>
And it indeed is a bug. The function guarantees to return false “if the number can be determined to be composite” and true for all primes, so it should err in only one way.<p>I would further improve the code by having it shortcut for all primes smaller than 31 (adding 29 and 31) or 63.
For context: Switzerland doesn't have evoting. This is just some big company trying to re-sell a evoting system to the government. It has been in the news a few times, due to software and cryptographic quality issues.
I would be very weary of changing such constants as this<p>19 should have been tested by a lookup table, there's no need to apply such heavy test to it<p>However, by changing that constant (if not properly verified) I'd worry it might change the primality test for some classes of numbers. Where this might be later manipulated to produce a weak key
Could someone explain why they've used a constant sp instead of hardcoding the primes? How was it created, did someone manually hardcoded the bits then converted into a number?
Can someone explain how such a simple and easily-testable bug existed in a seemingly-important system like this?<p>I don't know much about Swiss e-voting, but seems even the most brain-dead unit test of the IsProbablePrime function should have caught this.