# wagner
Python implementation of [Wagner's Algorithm for the Generalized Birthday Problem](https://link.springer.com/content/pdf/10.1007/3-540-45708-9_19.pdf).
This algorithm is used to solve what is known as the generalized birthday problem. Given a modulus $n$, and $k$ lists of random numbers $\\{L_1, L_2, ..., L_k\\}$, how can we find $k$ elements $\\{x_1, x_2, ..., x_k\\} : x_i \in L_i$ from those lists, such that they all sum to some constant $c$ mod $n$?
[Check out my full-length article on the subject](https://conduition.io/cryptography/wagner) for more detailed info. This repository is meant as a demonstration for practically minded and inquisitive readers.
## Usage
The primary export of this library is the `solve` method.
```python
>>> import wagner
>>> wagner.solve(2**16)
[50320, 16960, 11687, 52082, 17220, 47751, 11228, 54896]
>>> sum(_) % (2**16)
0
```
This method solves the generalized birthday problem for a given modulus $n$. The higher $n$ is, the more difficult it is to find a solution and the longer the algorithm will take.
At no cost, the caller can also choose a desired sum other than zero.
```python
n = 2 ** 16
sum(wagner.solve(n, 885)) % n # -> 885
```
To change the number of elements returned by `solve`, specify the height $H$ of the tree used to solve the problem. The number of elements in the solution will be $2^H$.
```python
len(wagner.solve(n, tree_height=2)) # -> 4
len(wagner.solve(n, tree_height=3)) # -> 8
len(wagner.solve(n, tree_height=4)) # -> 16
len(wagner.solve(n, tree_height=5)) # -> 32
```
To specify how the random elements are generated, provide a `generator` callback. By default, `wagner` uses `random.randrange(n)` to generate random values. A common use case for Wagner's Algorithm is to find inputs whose hashes sum to some desired number. To ensure `solve` returns the preimages and not the hash outputs, return `Lineage` instances from your `generator` callback. This class holds is basically an integer with pointers to the element(s) which created it.
```python
import random
import hashlib
import wagner
def hashfunc(r, n, index):
r_bytes = r.to_bytes((int.bit_length(n) + 7) // 8, 'big')
preimage = r_bytes + index.to_bytes(16, 'big')
h = hashlib.sha1(preimage).digest()
return int.from_bytes(h, 'big') % n
def generator(n, index):
r = random.randrange(0, n)
return wagner.Lineage(hashfunc(r, n, index), r)
if __name__ == "__main__":
n = 2 ** 128
preimages = wagner.solve(n, generator=generator)
print(sum(hashfunc(r, n, index) for index, r in enumerate(preimages)) % n) # -> 0
```
Raw data
{
"_id": null,
"home_page": "https://github.com/conduition/wagner",
"name": "wagner",
"maintainer": null,
"docs_url": null,
"requires_python": null,
"maintainer_email": null,
"keywords": "birthday,musig,attack,wagner,generalized birthday problem,k-sum,k sum",
"author": "conduition",
"author_email": "conduition@proton.me",
"download_url": "https://files.pythonhosted.org/packages/f7/bb/e14241449ed5b279388298226dcb6951b49409c0e2c77ac48c46009ba33b/wagner-0.0.2.tar.gz",
"platform": null,
"description": "# wagner\n\nPython implementation of [Wagner's Algorithm for the Generalized Birthday Problem](https://link.springer.com/content/pdf/10.1007/3-540-45708-9_19.pdf).\n\nThis algorithm is used to solve what is known as the generalized birthday problem. Given a modulus $n$, and $k$ lists of random numbers $\\\\{L_1, L_2, ..., L_k\\\\}$, how can we find $k$ elements $\\\\{x_1, x_2, ..., x_k\\\\} : x_i \\in L_i$ from those lists, such that they all sum to some constant $c$ mod $n$?\n\n[Check out my full-length article on the subject](https://conduition.io/cryptography/wagner) for more detailed info. This repository is meant as a demonstration for practically minded and inquisitive readers.\n\n## Usage\n\nThe primary export of this library is the `solve` method.\n\n```python\n>>> import wagner\n>>> wagner.solve(2**16)\n[50320, 16960, 11687, 52082, 17220, 47751, 11228, 54896]\n>>> sum(_) % (2**16)\n0\n```\n\nThis method solves the generalized birthday problem for a given modulus $n$. The higher $n$ is, the more difficult it is to find a solution and the longer the algorithm will take.\n\nAt no cost, the caller can also choose a desired sum other than zero.\n\n```python\nn = 2 ** 16\nsum(wagner.solve(n, 885)) % n # -> 885\n```\n\nTo change the number of elements returned by `solve`, specify the height $H$ of the tree used to solve the problem. The number of elements in the solution will be $2^H$.\n\n```python\nlen(wagner.solve(n, tree_height=2)) # -> 4\nlen(wagner.solve(n, tree_height=3)) # -> 8\nlen(wagner.solve(n, tree_height=4)) # -> 16\nlen(wagner.solve(n, tree_height=5)) # -> 32\n```\n\nTo specify how the random elements are generated, provide a `generator` callback. By default, `wagner` uses `random.randrange(n)` to generate random values. A common use case for Wagner's Algorithm is to find inputs whose hashes sum to some desired number. To ensure `solve` returns the preimages and not the hash outputs, return `Lineage` instances from your `generator` callback. This class holds is basically an integer with pointers to the element(s) which created it.\n\n```python\nimport random\nimport hashlib\nimport wagner\n\n\ndef hashfunc(r, n, index):\n r_bytes = r.to_bytes((int.bit_length(n) + 7) // 8, 'big')\n preimage = r_bytes + index.to_bytes(16, 'big')\n h = hashlib.sha1(preimage).digest()\n return int.from_bytes(h, 'big') % n\n\n\ndef generator(n, index):\n r = random.randrange(0, n)\n return wagner.Lineage(hashfunc(r, n, index), r)\n\n\nif __name__ == \"__main__\":\n n = 2 ** 128\n preimages = wagner.solve(n, generator=generator)\n print(sum(hashfunc(r, n, index) for index, r in enumerate(preimages)) % n) # -> 0\n```",
"bugtrack_url": null,
"license": null,
"summary": "Python implementation of Wagner's Algorithm for the Generalized Birthday Problem.",
"version": "0.0.2",
"project_urls": {
"Homepage": "https://github.com/conduition/wagner"
},
"split_keywords": [
"birthday",
"musig",
"attack",
"wagner",
"generalized birthday problem",
"k-sum",
"k sum"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "f7bbe14241449ed5b279388298226dcb6951b49409c0e2c77ac48c46009ba33b",
"md5": "5cc8aebfb781d41b70e3bab7ff7a7f60",
"sha256": "83d8d934c35988d477bee83e3dd8a73c77d72b2d25148b6b3e758ea0b537df9c"
},
"downloads": -1,
"filename": "wagner-0.0.2.tar.gz",
"has_sig": false,
"md5_digest": "5cc8aebfb781d41b70e3bab7ff7a7f60",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 5363,
"upload_time": "2023-08-15T17:07:50",
"upload_time_iso_8601": "2023-08-15T17:07:50.514201Z",
"url": "https://files.pythonhosted.org/packages/f7/bb/e14241449ed5b279388298226dcb6951b49409c0e2c77ac48c46009ba33b/wagner-0.0.2.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-08-15 17:07:50",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "conduition",
"github_project": "wagner",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "wagner"
}
JSON
