# Need a test suite for my RSA implementation

I have an assignment to build a software which can encrypt/decrypt by RSA method. I already did it, but my teacher said that I need to find a test suite (include: modulus, public key, private key) to test if my software runs correctly.

He needs real data which has already been tested by someone else and that data needs to be mentioned in lectures, books, reports, benchmarks, etc...

I tried to find them but I cannot :(. I'm very appreciated if you can help me. Thank you.

There are RSA keys pairs in the validation suite for the RSA part of FIPS 186-4 (see second part of this answer for details).

Because "encrypt/decrypt by RSA method" is not well-defined (for lack of indication of the padding method), there's no way to tell which Known Answer Test vectors for it fit the question's need.

Also, only the decryption code can be tested with fixed KAT: RSA encryption with proper random padding is not deterministic, thus its code needs to be modified (de-randomized) for testing against KAT.

FIPS 186-4 is a standard for digital signatures per a variety of methods, including several RSA-based. It has a test suite, with at the bottom of the page links to files with test vectors. The one for FIPS 186-4 RSA-based functions is 186-3rsatestvectors.zip. It contains several keys pairs. For example, SigGenPSS_186-3.txt starts with

[mod = 2048]

e = 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000086c94f


Note: $$\mathtt{mod}$$ is the bit size of the public modulus, expressed in decimal. $$\mathtt n$$, $$\mathtt e$$ and $$\mathtt d$$ are the public modulus, the public exponent, and the FIPS 186-4-mandated private exponent, expressed in hexadecimal. Therefore, $$\mathtt d$$ was obtained as $$\mathtt e^{-1}\bmod\lambda(\mathtt n)$$ (where $$\lambda$$ is Carmichael's function), but is usable just as $$\mathtt e^{-1}\bmod\varphi(\mathtt n)$$ would be (where $$\varphi$$ is Euler's totient), another common private exponent in RSA.

For the modulus $$n=pq$$ you need to verify that $$p$$ and $$q$$ are prime numbers. You can do this with a probabilistic primality test like Rabin-Miller. For the public key $$e$$ you need to verify that it is coprime to the euler totient $$\phi (n)$$ you can do this with the extended Euclidean algorithm. For the private key $$d$$ you need to verify that $$de \equiv 1 \pmod n$$. You can do this with the extended Euclidean algorithm.

• .First of all, I want to say thank you. I already did all of what you say (my software runs well I can say that), at this time the things that I need is some data are mentioned in lectures, books, reports, benchmarks,.... to test it (because my teacher doesn't accept any data that is generated randomly) – user63361 Nov 11 '18 at 13:20
• Ok what you need is a test vector suite. You can use NIST vectors available here: csrc.nist.gov/Projects/… – Youssef El Housni Nov 11 '18 at 13:30
• $de \equiv 1 \pmod n$ usually does not hold. $d\,e\equiv 1 \pmod{\lambda (n)}$ holds. $d\,e\equiv 1 \pmod{\phi (n)}$ holds for some variants of RSA key generation. Verification of $d$ is usually performed by computing $d\,e\bmod{\lambda (n)}=1$ when the factorization of $n$ is known, including derived from $(n,e,d)$; or checking that $x^{e\,d}\bmod n=x$ for a few $x\in[2,n-2]$, otherwise. – fgrieu Nov 11 '18 at 14:38

The most common way to generate test data for a cryptography algorithm is to use another implementation of this algorithm that you trust. This lets you generate as much test data as you like, with whatever key size, message size, etc. that you desire.

This is the way cryptography implementations are functionally validated in the real world. Sometimes it's done by using a known-good implementation, generating test data, and checking that the new implementation generates the same results. Sometimes it's done by running two or more implementations in parallel on the same inputs and checking that they generate the same results.

How, you may ask, was the very first implementation validated? It depends. Usually the very first implementation is written in the most straightforward manner possible. No optimizations, no side channel resistance and other complications. Then people carefully review it against the English or mathematical description of the algorithm. Then someone else independently writes their own implementation and compares the results with the first.

Most specifications of cryptographic algorithms contain a few sample inputs and outputs. In cryptography, these are called “test vectors”. NIST CAVP has longer lists of test vectors for algorithms that NIST approves of. Given the nature of cryptographic calculations, just getting one test vector right is usually enough to show that your implementation is basically correct in the nominal case, at least for the given key size and message size. But it isn't enough to have a lot of confidence in your code. You should at least test some different key sizes and message sizes. Usually the only way to obtain sufficient test data is by running one or more known-good implementation.

As an added difficulty, some algorithms are randomized, for example RSA-PSS signature and any form of encryption. To use test vectors, you need to be able to configure your implementation to use a “fake” random stream that is identical to the random stream used to generate the test vectors. To compare with another implementation, the two implementations need to use the same random stream. This isn't always possible. If you can't do that, you can make interoperability tests. For example, encrypt with one implementation and decrypt with another implementation.

OpenSSL is a popular cryptography library, but it isn't always easy to use. Cryptodome is a Python library that I find convenient to generate test vectors.