# CRYSTALS-Dilithium Python Implementation
This repository contains a pure python implementation of CRYSTALS-Dilithium
following (at the time of writing) the most recent
[specification](https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf)
(v3.1)
This project has followed [`kyber-py`](https://github.com/jack4818/kyber-py)
which is a pure-python implementation of CRYSTALS-Kyber and reuses a lot of
code.
## Disclaimer
:warning: **Under no circumstances should this be used for a cryptographic application.** :warning:
I have written `dilithium-py` as a way to learn about the way protocol works,
and to try and create a clean, well commented implementation which people can
learn from.
This code is not constant time, or written to be performant. Rather, it was
written so that reading though the pseudocode of the
[specification](https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf)
closely matches the code which we use within `dilithium.py` and supporting files.
### KATs
This implementation passes all the KAT vectors, generated from the reference
implementation version 3.1.
These tests, as well as other internal unit tests are the file
[`test_dilithium.py`](test_dilithium.py).
### Generating KAT files
This implementation is based off the most recent specification (v3.1).
There were
[breaking changes](https://github.com/pq-crystals/dilithium/commit/e989e691ae3d3f5933d012ab074bdc413ebc6fad)
to the KAT files submitted to NIST when Dilithium was updated to 3.1, so the
NIST KAT files will not match our code.
To deal with this, we generated our own KAT files from the
[reference implementation](https://github.com/pq-crystals/dilithium/releases/tag/v3.1)
for version 3.1. These are the files inside [assets](assets/).
### Dependencies
Originally, as with `kyber-py`, this project was planned to have zero
dependencies, however like `kyber-py`, to pass the KATs, I need a
deterministic CSRNG. The reference implementation uses
AES256 CTR DRBG. I have implemented this in [`ase256_ctr_drbg.py`](ase256_ctr_drbg.py).
However, I have not implemented AES itself, instead I import this from `pycryptodome`.
To install dependencies, run `pip -r install requirements`.
If you're happy to use system randomness (`os.urandom`) then you don't need
this dependency.
## Using dilithium-py
There are three functions exposed on the `Dilithium` class which are intended
for use:
- `Dilithium.keygen()`: generate a bit-packed keypair `(pk, sk)`
- `Dilithium.sign(sk, msg)`: generate a bit-packed signature `sig` from the message `msg` and bit-packed secret key `sk`.
- `Dilithium.verify(pk, msg, sig)`: verify that the bit-packed `sig` is valid for a given message `msg` and bit-packed public key `pk`.
To use `Dilithium()`, it must be initialised with a dictionary of the
protocol parameters. An example can be seen in `DEFAULT_PARAMETERS` in
the file [`dilithium.py`](dilithium.py)
Additionally, the class has been initialised with these default parameters,
so you can simply import the NIST level you want to play with:
#### Example
```python
>>> from dilithium import Dilithium2
>>>
>>> # Example of signing
>>> pk, sk = Dilithium2.keygen()
>>> msg = b"Your message signed by Dilithium"
>>> sig = Dilithium2.sign(sk, msg)
>>> assert Dilithium2.verify(pk, msg, sig)
>>>
>>> # Verification will fail with the wrong msg or pk
>>> assert not Dilithium2.verify(pk, b"", sig)
>>> pk_new, sk_new = Dilithium2.keygen()
>>> assert not Dilithium2.verify(pk_new, msg, sig)
```
The above example would also work with the other NIST levels
`Dilithium3` and `Dilithium5`.
## Future Plans
* **First plan**: Add documentation to the code
* Add examples for each of the functions
* Add documentation on how each of the components works
* Add documentation for working with DRBG and setting the seed
## Discussion of Implementation
### Polynomials
The file [`polynomials.py`](polynomials.py) contains the classes
`PolynomialRing` and
`Polynomial`. This implements the univariate polynomial ring
$$
R_q = \mathbb{F}_q[X] /(X^n + 1)
$$
The implementation is inspired by `SageMath` and you can create the
ring $R_{11} = \mathbb{F}_{11}[X] /(X^8 + 1)$ in the following way:
#### Example
```python
>>> R = PolynomialRing(11, 8)
>>> x = R.gen()
>>> f = 3*x**3 + 4*x**7
>>> g = R.random_element(); g
5 + x^2 + 5*x^3 + 4*x^4 + x^5 + 3*x^6 + 8*x^7
>>> f*g
8 + 9*x + 10*x^3 + 7*x^4 + 2*x^5 + 5*x^6 + 10*x^7
>>> f + f
6*x^3 + 8*x^7
>>> g - g
0
```
### Modules
The file [`modules.py`](modules.py) contains the classes `Module` and `Matrix`.
A module is a generalisation of a vector space, where the field
of scalars is replaced with a ring. In the case of Dilithium, we
need the module with the ring $R_q$ as described above.
`Matrix` allows elements of the module to be of size $m \times n$
For Dilithium, we need vectors of length $k$ and $l$ and a matrix
of size $l \times k$.
As an example of the operations we can perform with out `Module`
lets revisit the ring from the previous example:
#### Example
```python
>>> R = PolynomialRing(11, 8)
>>> x = R.gen()
>>>
>>> M = Module(R)
>>> # We create a matrix by feeding the coefficients to M
>>> A = M([[x + 3*x**2, 4 + 3*x**7], [3*x**3 + 9*x**7, x**4]])
>>> A
[ x + 3*x^2, 4 + 3*x^7]
[3*x^3 + 9*x^7, x^4]
>>> # We can add and subtract matricies of the same size
>>> A + A
[ 2*x + 6*x^2, 8 + 6*x^7]
[6*x^3 + 7*x^7, 2*x^4]
>>> A - A
[0, 0]
[0, 0]
>>> # A vector can be constructed by a list of coefficents
>>> v = M([3*x**5, x])
>>> v
[3*x^5, x]
>>> # We can compute the transpose
>>> v.transpose()
[3*x^5]
[ x]
>>> v + v
[6*x^5, 2*x]
>>> # We can also compute the transpose in place
>>> v.transpose_self()
[3*x^5]
[ x]
>>> v + v
[6*x^5]
[ 2*x]
>>> # Matrix multiplication follows python standards and is denoted by @
>>> A @ v
[8 + 4*x + 3*x^6 + 9*x^7]
[ 2 + 6*x^4 + x^5]
```
### Number Theoretic Transform
**TODO**: More details about the NTT.
We can transform polynomials to NTT form and from NTT form
with `poly.to_ntt()` and `poly.from_ntt()`.
When we perform operations between polynomials, `(+, -, *)`
either both or neither must be in NTT form.
```py
>>> f = R.random_element()
>>> f == f.to_ntt().from_ntt()
True
>>> g = R.random_element()
>>> h = f*g
>>> h == (f.to_ntt() * g.to_ntt()).from_ntt()
True
```
While writing this README, performing multiplication of of polynomials
in NTT form is about 100x faster when working with the ring used by
Dilithium.
```py
>>> # Lets work in the ring we use for Dilithium
>>> R = Dilithium2.R
>>> # Generate some random elements
>>> f = R.random_element()
>>> g = R.random_element()
>>> # Takes about 10 seconds to perform 1000 multiplications
>>> timeit.timeit("f*g", globals=globals(), number=1000)
9.621509193995735
>>> # Now lets convert to NTT and try again
>>> f.to_ntt()
>>> g.to_ntt()
>>> # Now it only takes ~0.1s to perform 1000 multiplications!
>>> timeit.timeit("f*g", globals=globals(), number=1000)
0.12979038299818058
```
These functions extend to modules
```py
>>> M = Dilithium2.M
>>> R = Dilithium2.R
>>> v = M([R.random_element(), R.random_element()])
>>> u = M([R.random_element(), R.random_element()]).transpose()
>>> A = u @ v
>>> A == (u.to_ntt() @ v.to_ntt()).from_ntt()
True
```
As operations on the module are just operations between elements,
we expect a similar 100x speed up when working in NTT form:
```py
>>> u = M([R.random_element(), R.random_element()]).transpose()
>>> v = M([R.random_element(), R.random_element()])
>>> timeit.timeit("u@v", globals=globals(), number=1000)
38.39359304799291
>>> u = u.to_ntt()
>>> v = v.to_ntt()
>>> timeit.timeit("u@v", globals=globals(), number=1000)
0.495470915993792
```
### Bit Packing
```
TODO
```
### Random Sampling
```
TODO
```
### AES256-CTR-DRBG
```
TODO
```
Raw data
{
"_id": null,
"home_page": "https://eshard.com",
"name": "dilithium",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "PQC,Digital-Signatures,Dilithium",
"author": "eshard",
"author_email": "",
"download_url": "https://files.pythonhosted.org/packages/f9/71/24a9985c9cc1be1bee498d0bb868c7686aa315033c2545ecf10964f65e33/dilithium-1.0.6.tar.gz",
"platform": null,
"description": "# CRYSTALS-Dilithium Python Implementation\n\nThis repository contains a pure python implementation of CRYSTALS-Dilithium \nfollowing (at the time of writing) the most recent \n[specification](https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf)\n(v3.1)\n\nThis project has followed [`kyber-py`](https://github.com/jack4818/kyber-py)\nwhich is a pure-python implementation of CRYSTALS-Kyber and reuses a lot of\ncode. \n\n## Disclaimer\n\n:warning: **Under no circumstances should this be used for a cryptographic application.** :warning:\n\nI have written `dilithium-py` as a way to learn about the way protocol works,\nand to try and create a clean, well commented implementation which people can\nlearn from.\n\nThis code is not constant time, or written to be performant. Rather, it was \nwritten so that reading though the pseudocode of the \n[specification](https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf)\nclosely matches the code which we use within `dilithium.py` and supporting files.\n\n### KATs\n\nThis implementation passes all the KAT vectors, generated from the reference\nimplementation version 3.1.\n\nThese tests, as well as other internal unit tests are the file \n[`test_dilithium.py`](test_dilithium.py).\n\n### Generating KAT files\n\nThis implementation is based off the most recent specification (v3.1). \nThere were \n[breaking changes](https://github.com/pq-crystals/dilithium/commit/e989e691ae3d3f5933d012ab074bdc413ebc6fad) \nto the KAT files submitted to NIST when Dilithium was updated to 3.1, so the\nNIST KAT files will not match our code.\n\nTo deal with this, we generated our own KAT files from the \n[reference implementation](https://github.com/pq-crystals/dilithium/releases/tag/v3.1)\nfor version 3.1. These are the files inside [assets](assets/).\n\n### Dependencies\n\nOriginally, as with `kyber-py`, this project was planned to have zero\ndependencies, however like `kyber-py`, to pass the KATs, I need a \ndeterministic CSRNG. The reference implementation uses\nAES256 CTR DRBG. I have implemented this in [`ase256_ctr_drbg.py`](ase256_ctr_drbg.py). \nHowever, I have not implemented AES itself, instead I import this from `pycryptodome`.\n\nTo install dependencies, run `pip -r install requirements`.\n\nIf you're happy to use system randomness (`os.urandom`) then you don't need\nthis dependency.\n\n## Using dilithium-py\n\nThere are three functions exposed on the `Dilithium` class which are intended\nfor use:\n\n- `Dilithium.keygen()`: generate a bit-packed keypair `(pk, sk)`\n- `Dilithium.sign(sk, msg)`: generate a bit-packed signature `sig` from the message `msg` and bit-packed secret key `sk`.\n- `Dilithium.verify(pk, msg, sig)`: verify that the bit-packed `sig` is valid for a given message `msg` and bit-packed public key `pk`.\n\nTo use `Dilithium()`, it must be initialised with a dictionary of the \nprotocol parameters. An example can be seen in `DEFAULT_PARAMETERS` in\nthe file [`dilithium.py`](dilithium.py)\n\nAdditionally, the class has been initialised with these default parameters, \nso you can simply import the NIST level you want to play with:\n\n#### Example\n\n```python\n>>> from dilithium import Dilithium2\n>>>\n>>> # Example of signing\n>>> pk, sk = Dilithium2.keygen()\n>>> msg = b\"Your message signed by Dilithium\"\n>>> sig = Dilithium2.sign(sk, msg)\n>>> assert Dilithium2.verify(pk, msg, sig)\n>>>\n>>> # Verification will fail with the wrong msg or pk\n>>> assert not Dilithium2.verify(pk, b\"\", sig)\n>>> pk_new, sk_new = Dilithium2.keygen()\n>>> assert not Dilithium2.verify(pk_new, msg, sig)\n```\n\nThe above example would also work with the other NIST levels\n`Dilithium3` and `Dilithium5`.\n\n\n## Future Plans\n\n* **First plan**: Add documentation to the code\n* Add examples for each of the functions\n* Add documentation on how each of the components works\n* Add documentation for working with DRBG and setting the seed\n\n## Discussion of Implementation\n\n### Polynomials\n\nThe file [`polynomials.py`](polynomials.py) contains the classes \n`PolynomialRing` and \n`Polynomial`. This implements the univariate polynomial ring\n\n$$\nR_q = \\mathbb{F}_q[X] /(X^n + 1) \n$$\n\nThe implementation is inspired by `SageMath` and you can create the\nring $R_{11} = \\mathbb{F}_{11}[X] /(X^8 + 1)$ in the following way:\n\n#### Example\n\n```python\n>>> R = PolynomialRing(11, 8)\n>>> x = R.gen()\n>>> f = 3*x**3 + 4*x**7\n>>> g = R.random_element(); g\n5 + x^2 + 5*x^3 + 4*x^4 + x^5 + 3*x^6 + 8*x^7\n>>> f*g\n8 + 9*x + 10*x^3 + 7*x^4 + 2*x^5 + 5*x^6 + 10*x^7\n>>> f + f\n6*x^3 + 8*x^7\n>>> g - g\n0\n```\n\n### Modules\n\nThe file [`modules.py`](modules.py) contains the classes `Module` and `Matrix`.\nA module is a generalisation of a vector space, where the field\nof scalars is replaced with a ring. In the case of Dilithium, we \nneed the module with the ring $R_q$ as described above. \n\n`Matrix` allows elements of the module to be of size $m \\times n$\nFor Dilithium, we need vectors of length $k$ and $l$ and a matrix\nof size $l \\times k$. \n\nAs an example of the operations we can perform with out `Module`\nlets revisit the ring from the previous example:\n\n#### Example\n\n```python\n>>> R = PolynomialRing(11, 8)\n>>> x = R.gen()\n>>>\n>>> M = Module(R)\n>>> # We create a matrix by feeding the coefficients to M\n>>> A = M([[x + 3*x**2, 4 + 3*x**7], [3*x**3 + 9*x**7, x**4]])\n>>> A\n[ x + 3*x^2, 4 + 3*x^7]\n[3*x^3 + 9*x^7, x^4]\n>>> # We can add and subtract matricies of the same size\n>>> A + A\n[ 2*x + 6*x^2, 8 + 6*x^7]\n[6*x^3 + 7*x^7, 2*x^4]\n>>> A - A\n[0, 0]\n[0, 0]\n>>> # A vector can be constructed by a list of coefficents\n>>> v = M([3*x**5, x])\n>>> v\n[3*x^5, x]\n>>> # We can compute the transpose\n>>> v.transpose()\n[3*x^5]\n[ x]\n>>> v + v\n[6*x^5, 2*x]\n>>> # We can also compute the transpose in place\n>>> v.transpose_self()\n[3*x^5]\n[ x]\n>>> v + v\n[6*x^5]\n[ 2*x]\n>>> # Matrix multiplication follows python standards and is denoted by @\n>>> A @ v\n[8 + 4*x + 3*x^6 + 9*x^7]\n[ 2 + 6*x^4 + x^5]\n```\n\n### Number Theoretic Transform\n\n**TODO**: More details about the NTT.\n\nWe can transform polynomials to NTT form and from NTT form\nwith `poly.to_ntt()` and `poly.from_ntt()`.\n\nWhen we perform operations between polynomials, `(+, -, *)`\neither both or neither must be in NTT form.\n\n```py\n>>> f = R.random_element()\n>>> f == f.to_ntt().from_ntt()\nTrue\n>>> g = R.random_element()\n>>> h = f*g\n>>> h == (f.to_ntt() * g.to_ntt()).from_ntt()\nTrue\n```\n\nWhile writing this README, performing multiplication of of polynomials\nin NTT form is about 100x faster when working with the ring used by\nDilithium.\n\n```py\n>>> # Lets work in the ring we use for Dilithium\n>>> R = Dilithium2.R\n>>> # Generate some random elements\n>>> f = R.random_element()\n>>> g = R.random_element()\n>>> # Takes about 10 seconds to perform 1000 multiplications\n>>> timeit.timeit(\"f*g\", globals=globals(), number=1000)\n9.621509193995735\n>>> # Now lets convert to NTT and try again\n>>> f.to_ntt()\n>>> g.to_ntt()\n>>> # Now it only takes ~0.1s to perform 1000 multiplications!\n>>> timeit.timeit(\"f*g\", globals=globals(), number=1000)\n0.12979038299818058\n```\n\nThese functions extend to modules\n\n```py\n>>> M = Dilithium2.M\n>>> R = Dilithium2.R\n>>> v = M([R.random_element(), R.random_element()])\n>>> u = M([R.random_element(), R.random_element()]).transpose()\n>>> A = u @ v\n>>> A == (u.to_ntt() @ v.to_ntt()).from_ntt()\nTrue\n```\n\nAs operations on the module are just operations between elements, \nwe expect a similar 100x speed up when working in NTT form:\n\n```py\n>>> u = M([R.random_element(), R.random_element()]).transpose()\n>>> v = M([R.random_element(), R.random_element()])\n>>> timeit.timeit(\"u@v\", globals=globals(), number=1000)\n38.39359304799291\n>>> u = u.to_ntt()\n>>> v = v.to_ntt()\n>>> timeit.timeit(\"u@v\", globals=globals(), number=1000)\n0.495470915993792\n```\n\n### Bit Packing\n\n```\nTODO\n```\n\n### Random Sampling\n\n```\nTODO\n```\n\n### AES256-CTR-DRBG\n\n```\nTODO\n```\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "CRYSTALS-Dilithium for eShard",
"version": "1.0.6",
"project_urls": {
"Homepage": "https://eshard.com"
},
"split_keywords": [
"pqc",
"digital-signatures",
"dilithium"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "cb4e0c9a3c52bb3ddee599aaa8b575a125d8b406031361b6cf840885cfb7951c",
"md5": "f0f1cee31fe8844ac673f639351a8133",
"sha256": "2f9efd0e4f5a0ddc4b9ef71aca60bd0a0f9de57c9b5bcac5cf89592f7b4e0f14"
},
"downloads": -1,
"filename": "dilithium-1.0.6-py3-none-any.whl",
"has_sig": false,
"md5_digest": "f0f1cee31fe8844ac673f639351a8133",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 26436,
"upload_time": "2023-11-21T13:18:13",
"upload_time_iso_8601": "2023-11-21T13:18:13.977100Z",
"url": "https://files.pythonhosted.org/packages/cb/4e/0c9a3c52bb3ddee599aaa8b575a125d8b406031361b6cf840885cfb7951c/dilithium-1.0.6-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "f97124a9985c9cc1be1bee498d0bb868c7686aa315033c2545ecf10964f65e33",
"md5": "2c0a58c372fd89309c757ecc5184500e",
"sha256": "3d97858ef502b88337006a5363f8fa3e2f55ae958f6051015a096d9ea5ad39ea"
},
"downloads": -1,
"filename": "dilithium-1.0.6.tar.gz",
"has_sig": false,
"md5_digest": "2c0a58c372fd89309c757ecc5184500e",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 26285,
"upload_time": "2023-11-21T13:18:15",
"upload_time_iso_8601": "2023-11-21T13:18:15.725195Z",
"url": "https://files.pythonhosted.org/packages/f9/71/24a9985c9cc1be1bee498d0bb868c7686aa315033c2545ecf10964f65e33/dilithium-1.0.6.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-11-21 13:18:15",
"github": false,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"lcname": "dilithium"
}
JSON