1565 lines
90 KiB
HTML
1565 lines
90 KiB
HTML
<!DOCTYPE html>
|
||
<html class="writer-html5" lang="en" >
|
||
<head>
|
||
<meta charset="utf-8" />
|
||
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
|
||
<link rel="shortcut icon" href="../img/favicon.ico" />
|
||
<title>Elliptic Curve Cryptography - CryptoTools documentation</title>
|
||
<link rel="stylesheet" href="../css/theme.css" />
|
||
<link rel="stylesheet" href="../css/theme_extra.css" />
|
||
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.8.0/styles/github.min.css" />
|
||
<link href="../assets/_mkdocstrings.css" rel="stylesheet" />
|
||
|
||
<script>
|
||
// Current page data
|
||
var mkdocs_page_name = "Elliptic Curve Cryptography";
|
||
var mkdocs_page_input_path = "ecc.md";
|
||
var mkdocs_page_url = null;
|
||
</script>
|
||
|
||
<!--[if lt IE 9]>
|
||
<script src="../js/html5shiv.min.js"></script>
|
||
<![endif]-->
|
||
<script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.8.0/highlight.min.js"></script>
|
||
<script>hljs.highlightAll();</script>
|
||
</head>
|
||
|
||
<body class="wy-body-for-nav" role="document">
|
||
|
||
<div class="wy-grid-for-nav">
|
||
<nav data-toggle="wy-nav-shift" class="wy-nav-side stickynav">
|
||
<div class="wy-side-scroll">
|
||
<div class="wy-side-nav-search">
|
||
<a href=".." class="icon icon-home"> CryptoTools documentation
|
||
</a>
|
||
</div>
|
||
|
||
<div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu">
|
||
<ul>
|
||
<li class="toctree-l1"><a class="reference internal" href="../introduction/">Introduction</a>
|
||
</li>
|
||
</ul>
|
||
<ul>
|
||
<li class="toctree-l1"><a class="reference internal" href="../installation/">Installation</a>
|
||
</li>
|
||
</ul>
|
||
<p class="caption"><span class="caption-text">Low-level cryptographic</span></p>
|
||
<ul class="current">
|
||
<li class="toctree-l1"><a class="reference internal" href="../number-theory/">Number theory</a>
|
||
</li>
|
||
<li class="toctree-l1"><a class="reference internal" href="../group-theory/">Group theory</a>
|
||
</li>
|
||
<li class="toctree-l1"><a class="reference internal" href="../curves/">Curves</a>
|
||
</li>
|
||
<li class="toctree-l1 current"><a class="reference internal current" href="#">Elliptic Curve Cryptography</a>
|
||
<ul class="current">
|
||
<li class="toctree-l2"><a class="reference internal" href="#Cryptotools.Groups.elliptic">elliptic</a>
|
||
</li>
|
||
<li class="toctree-l2"><a class="reference internal" href="#Cryptotools.Groups.elliptic.Elliptic">Elliptic</a>
|
||
<ul>
|
||
<li class="toctree-l3"><a class="reference internal" href="#Cryptotools.Groups.elliptic.Elliptic.cofactor">cofactor</a>
|
||
</li>
|
||
<li class="toctree-l3"><a class="reference internal" href="#Cryptotools.Groups.elliptic.Elliptic.order">order</a>
|
||
</li>
|
||
<li class="toctree-l3"><a class="reference internal" href="#Cryptotools.Groups.elliptic.Elliptic.add">add</a>
|
||
</li>
|
||
<li class="toctree-l3"><a class="reference internal" href="#Cryptotools.Groups.elliptic.Elliptic.curve25519">curve25519</a>
|
||
</li>
|
||
<li class="toctree-l3"><a class="reference internal" href="#Cryptotools.Groups.elliptic.Elliptic.findOrder">findOrder</a>
|
||
</li>
|
||
<li class="toctree-l3"><a class="reference internal" href="#Cryptotools.Groups.elliptic.Elliptic.getQuadraticResidues">getQuadraticResidues</a>
|
||
</li>
|
||
<li class="toctree-l3"><a class="reference internal" href="#Cryptotools.Groups.elliptic.Elliptic.pointExist">pointExist</a>
|
||
</li>
|
||
<li class="toctree-l3"><a class="reference internal" href="#Cryptotools.Groups.elliptic.Elliptic.pointsE">pointsE</a>
|
||
</li>
|
||
<li class="toctree-l3"><a class="reference internal" href="#Cryptotools.Groups.elliptic.Elliptic.quadraticResidues">quadraticResidues</a>
|
||
</li>
|
||
<li class="toctree-l3"><a class="reference internal" href="#Cryptotools.Groups.elliptic.Elliptic.scalar">scalar</a>
|
||
</li>
|
||
</ul>
|
||
</li>
|
||
</ul>
|
||
</li>
|
||
</ul>
|
||
<p class="caption"><span class="caption-text">Public Keys</span></p>
|
||
<ul>
|
||
<li class="toctree-l1"><a class="reference internal" href="../rsa/">RSA</a>
|
||
</li>
|
||
</ul>
|
||
<p class="caption"><span class="caption-text">Utils</span></p>
|
||
<ul>
|
||
<li class="toctree-l1"><a class="reference internal" href="../utils/">Utils</a>
|
||
</li>
|
||
</ul>
|
||
<p class="caption"><span class="caption-text">Examples</span></p>
|
||
<ul>
|
||
<li class="toctree-l1"><a class="reference internal" href="../example-rsa-keys/">Generating RSA Keys</a>
|
||
</li>
|
||
<li class="toctree-l1"><a class="reference internal" href="../example-curves/">Generating Curves</a>
|
||
</li>
|
||
</ul>
|
||
</div>
|
||
</div>
|
||
</nav>
|
||
|
||
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">
|
||
<nav class="wy-nav-top" role="navigation" aria-label="Mobile navigation menu">
|
||
<i data-toggle="wy-nav-top" class="fa fa-bars"></i>
|
||
<a href="..">CryptoTools documentation</a>
|
||
|
||
</nav>
|
||
<div class="wy-nav-content">
|
||
<div class="rst-content"><div role="navigation" aria-label="breadcrumbs navigation">
|
||
<ul class="wy-breadcrumbs">
|
||
<li><a href=".." class="icon icon-home" aria-label="Docs"></a></li>
|
||
<li class="breadcrumb-item">Low-level cryptographic</li>
|
||
<li class="breadcrumb-item active">Elliptic Curve Cryptography</li>
|
||
<li class="wy-breadcrumbs-aside">
|
||
</li>
|
||
</ul>
|
||
<hr/>
|
||
</div>
|
||
<div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
|
||
<div class="section" itemprop="articleBody">
|
||
|
||
<h1 id="elliptic-curve-cryptography">Elliptic Curve Cryptography</h1>
|
||
|
||
|
||
<div class="doc doc-object doc-module">
|
||
|
||
|
||
|
||
<a id="Cryptotools.Groups.elliptic"></a>
|
||
<div class="doc doc-contents first">
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
<div class="doc doc-children">
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
<div class="doc doc-object doc-class">
|
||
|
||
|
||
|
||
<h2 id="Cryptotools.Groups.elliptic.Elliptic" class="doc doc-heading">
|
||
<code>Elliptic</code>
|
||
|
||
|
||
</h2>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
|
||
|
||
<p>This class generate a group for Elliptic Curve
|
||
An Elliptic Curve is a algebraic group from the Group theory branch.</p>
|
||
<p>An Elliptic Curve is a set of points from this equation (Weierstrass equations): $y2 = x3 + ax + b$</p>
|
||
<p>To generate points of $E(F_p)$, first, we need to generate all square modulos
|
||
The, for all X, we increment it until $X < n$ and if exist a square modulos
|
||
It's a point of the list $E(F_p)$</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Attributes:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<b><code>n</code></b>
|
||
(<code><span title="Integer">Integer</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>It's the modulo</p>
|
||
</div>
|
||
</li>
|
||
<li>
|
||
<b><code>a</code></b>
|
||
(<code><span title="Integer">Integer</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
|
||
</div>
|
||
</li>
|
||
<li>
|
||
<b><code>b</code></b>
|
||
(<code><span title="Integer">Integer</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
|
||
</div>
|
||
</li>
|
||
<li>
|
||
<b><code>squares</code></b>
|
||
(<code><span title="Dict">Dict</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Dictionary which contain quadratic nonresidue. The key is the quadratic nonresidue and for each entry, we have a list of point for the quadratic nonresidue</p>
|
||
</div>
|
||
</li>
|
||
<li>
|
||
<b><code>E</code></b>
|
||
(<code><span title="List">List</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>List of all Points</p>
|
||
</div>
|
||
</li>
|
||
<li>
|
||
<b><code>order</code></b>
|
||
(<code><span title="Int">Int</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Order (length) of the group</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
|
||
|
||
|
||
|
||
|
||
<details class="quote">
|
||
<summary>Source code in <code>Cryptotools/Groups/elliptic.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal"> 8</span>
|
||
<span class="normal"> 9</span>
|
||
<span class="normal"> 10</span>
|
||
<span class="normal"> 11</span>
|
||
<span class="normal"> 12</span>
|
||
<span class="normal"> 13</span>
|
||
<span class="normal"> 14</span>
|
||
<span class="normal"> 15</span>
|
||
<span class="normal"> 16</span>
|
||
<span class="normal"> 17</span>
|
||
<span class="normal"> 18</span>
|
||
<span class="normal"> 19</span>
|
||
<span class="normal"> 20</span>
|
||
<span class="normal"> 21</span>
|
||
<span class="normal"> 22</span>
|
||
<span class="normal"> 23</span>
|
||
<span class="normal"> 24</span>
|
||
<span class="normal"> 25</span>
|
||
<span class="normal"> 26</span>
|
||
<span class="normal"> 27</span>
|
||
<span class="normal"> 28</span>
|
||
<span class="normal"> 29</span>
|
||
<span class="normal"> 30</span>
|
||
<span class="normal"> 31</span>
|
||
<span class="normal"> 32</span>
|
||
<span class="normal"> 33</span>
|
||
<span class="normal"> 34</span>
|
||
<span class="normal"> 35</span>
|
||
<span class="normal"> 36</span>
|
||
<span class="normal"> 37</span>
|
||
<span class="normal"> 38</span>
|
||
<span class="normal"> 39</span>
|
||
<span class="normal"> 40</span>
|
||
<span class="normal"> 41</span>
|
||
<span class="normal"> 42</span>
|
||
<span class="normal"> 43</span>
|
||
<span class="normal"> 44</span>
|
||
<span class="normal"> 45</span>
|
||
<span class="normal"> 46</span>
|
||
<span class="normal"> 47</span>
|
||
<span class="normal"> 48</span>
|
||
<span class="normal"> 49</span>
|
||
<span class="normal"> 50</span>
|
||
<span class="normal"> 51</span>
|
||
<span class="normal"> 52</span>
|
||
<span class="normal"> 53</span>
|
||
<span class="normal"> 54</span>
|
||
<span class="normal"> 55</span>
|
||
<span class="normal"> 56</span>
|
||
<span class="normal"> 57</span>
|
||
<span class="normal"> 58</span>
|
||
<span class="normal"> 59</span>
|
||
<span class="normal"> 60</span>
|
||
<span class="normal"> 61</span>
|
||
<span class="normal"> 62</span>
|
||
<span class="normal"> 63</span>
|
||
<span class="normal"> 64</span>
|
||
<span class="normal"> 65</span>
|
||
<span class="normal"> 66</span>
|
||
<span class="normal"> 67</span>
|
||
<span class="normal"> 68</span>
|
||
<span class="normal"> 69</span>
|
||
<span class="normal"> 70</span>
|
||
<span class="normal"> 71</span>
|
||
<span class="normal"> 72</span>
|
||
<span class="normal"> 73</span>
|
||
<span class="normal"> 74</span>
|
||
<span class="normal"> 75</span>
|
||
<span class="normal"> 76</span>
|
||
<span class="normal"> 77</span>
|
||
<span class="normal"> 78</span>
|
||
<span class="normal"> 79</span>
|
||
<span class="normal"> 80</span>
|
||
<span class="normal"> 81</span>
|
||
<span class="normal"> 82</span>
|
||
<span class="normal"> 83</span>
|
||
<span class="normal"> 84</span>
|
||
<span class="normal"> 85</span>
|
||
<span class="normal"> 86</span>
|
||
<span class="normal"> 87</span>
|
||
<span class="normal"> 88</span>
|
||
<span class="normal"> 89</span>
|
||
<span class="normal"> 90</span>
|
||
<span class="normal"> 91</span>
|
||
<span class="normal"> 92</span>
|
||
<span class="normal"> 93</span>
|
||
<span class="normal"> 94</span>
|
||
<span class="normal"> 95</span>
|
||
<span class="normal"> 96</span>
|
||
<span class="normal"> 97</span>
|
||
<span class="normal"> 98</span>
|
||
<span class="normal"> 99</span>
|
||
<span class="normal">100</span>
|
||
<span class="normal">101</span>
|
||
<span class="normal">102</span>
|
||
<span class="normal">103</span>
|
||
<span class="normal">104</span>
|
||
<span class="normal">105</span>
|
||
<span class="normal">106</span>
|
||
<span class="normal">107</span>
|
||
<span class="normal">108</span>
|
||
<span class="normal">109</span>
|
||
<span class="normal">110</span>
|
||
<span class="normal">111</span>
|
||
<span class="normal">112</span>
|
||
<span class="normal">113</span>
|
||
<span class="normal">114</span>
|
||
<span class="normal">115</span>
|
||
<span class="normal">116</span>
|
||
<span class="normal">117</span>
|
||
<span class="normal">118</span>
|
||
<span class="normal">119</span>
|
||
<span class="normal">120</span>
|
||
<span class="normal">121</span>
|
||
<span class="normal">122</span>
|
||
<span class="normal">123</span>
|
||
<span class="normal">124</span>
|
||
<span class="normal">125</span>
|
||
<span class="normal">126</span>
|
||
<span class="normal">127</span>
|
||
<span class="normal">128</span>
|
||
<span class="normal">129</span>
|
||
<span class="normal">130</span>
|
||
<span class="normal">131</span>
|
||
<span class="normal">132</span>
|
||
<span class="normal">133</span>
|
||
<span class="normal">134</span>
|
||
<span class="normal">135</span>
|
||
<span class="normal">136</span>
|
||
<span class="normal">137</span>
|
||
<span class="normal">138</span>
|
||
<span class="normal">139</span>
|
||
<span class="normal">140</span>
|
||
<span class="normal">141</span>
|
||
<span class="normal">142</span>
|
||
<span class="normal">143</span>
|
||
<span class="normal">144</span>
|
||
<span class="normal">145</span>
|
||
<span class="normal">146</span>
|
||
<span class="normal">147</span>
|
||
<span class="normal">148</span>
|
||
<span class="normal">149</span>
|
||
<span class="normal">150</span>
|
||
<span class="normal">151</span>
|
||
<span class="normal">152</span>
|
||
<span class="normal">153</span>
|
||
<span class="normal">154</span>
|
||
<span class="normal">155</span>
|
||
<span class="normal">156</span>
|
||
<span class="normal">157</span>
|
||
<span class="normal">158</span>
|
||
<span class="normal">159</span>
|
||
<span class="normal">160</span>
|
||
<span class="normal">161</span>
|
||
<span class="normal">162</span>
|
||
<span class="normal">163</span>
|
||
<span class="normal">164</span>
|
||
<span class="normal">165</span>
|
||
<span class="normal">166</span>
|
||
<span class="normal">167</span>
|
||
<span class="normal">168</span>
|
||
<span class="normal">169</span>
|
||
<span class="normal">170</span>
|
||
<span class="normal">171</span>
|
||
<span class="normal">172</span>
|
||
<span class="normal">173</span>
|
||
<span class="normal">174</span>
|
||
<span class="normal">175</span>
|
||
<span class="normal">176</span>
|
||
<span class="normal">177</span>
|
||
<span class="normal">178</span>
|
||
<span class="normal">179</span>
|
||
<span class="normal">180</span>
|
||
<span class="normal">181</span>
|
||
<span class="normal">182</span>
|
||
<span class="normal">183</span>
|
||
<span class="normal">184</span>
|
||
<span class="normal">185</span>
|
||
<span class="normal">186</span>
|
||
<span class="normal">187</span>
|
||
<span class="normal">188</span>
|
||
<span class="normal">189</span>
|
||
<span class="normal">190</span>
|
||
<span class="normal">191</span>
|
||
<span class="normal">192</span>
|
||
<span class="normal">193</span>
|
||
<span class="normal">194</span>
|
||
<span class="normal">195</span>
|
||
<span class="normal">196</span>
|
||
<span class="normal">197</span>
|
||
<span class="normal">198</span>
|
||
<span class="normal">199</span>
|
||
<span class="normal">200</span>
|
||
<span class="normal">201</span>
|
||
<span class="normal">202</span>
|
||
<span class="normal">203</span>
|
||
<span class="normal">204</span>
|
||
<span class="normal">205</span>
|
||
<span class="normal">206</span>
|
||
<span class="normal">207</span>
|
||
<span class="normal">208</span>
|
||
<span class="normal">209</span>
|
||
<span class="normal">210</span>
|
||
<span class="normal">211</span>
|
||
<span class="normal">212</span>
|
||
<span class="normal">213</span>
|
||
<span class="normal">214</span>
|
||
<span class="normal">215</span>
|
||
<span class="normal">216</span>
|
||
<span class="normal">217</span>
|
||
<span class="normal">218</span>
|
||
<span class="normal">219</span>
|
||
<span class="normal">220</span>
|
||
<span class="normal">221</span>
|
||
<span class="normal">222</span>
|
||
<span class="normal">223</span>
|
||
<span class="normal">224</span>
|
||
<span class="normal">225</span>
|
||
<span class="normal">226</span>
|
||
<span class="normal">227</span>
|
||
<span class="normal">228</span>
|
||
<span class="normal">229</span>
|
||
<span class="normal">230</span>
|
||
<span class="normal">231</span>
|
||
<span class="normal">232</span>
|
||
<span class="normal">233</span>
|
||
<span class="normal">234</span>
|
||
<span class="normal">235</span>
|
||
<span class="normal">236</span>
|
||
<span class="normal">237</span>
|
||
<span class="normal">238</span>
|
||
<span class="normal">239</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">class</span><span class="w"> </span><span class="nc">Elliptic</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This class generate a group for Elliptic Curve</span>
|
||
<span class="sd"> An Elliptic Curve is a algebraic group from the Group theory branch.</span>
|
||
|
||
<span class="sd"> An Elliptic Curve is a set of points from this equation (Weierstrass equations): $y2 = x3 + ax + b$</span>
|
||
|
||
|
||
<span class="sd"> To generate points of $E(F_p)$, first, we need to generate all square modulos</span>
|
||
<span class="sd"> The, for all X, we increment it until $X < n$ and if exist a square modulos</span>
|
||
<span class="sd"> It's a point of the list $E(F_p)$</span>
|
||
|
||
<span class="sd"> Attributes:</span>
|
||
<span class="sd"> n (Integer): It's the modulo</span>
|
||
<span class="sd"> a (Integer): </span>
|
||
<span class="sd"> b (Integer): </span>
|
||
<span class="sd"> squares (Dict): Dictionary which contain quadratic nonresidue. The key is the quadratic nonresidue and for each entry, we have a list of point for the quadratic nonresidue</span>
|
||
<span class="sd"> E (List): List of all Points</span>
|
||
<span class="sd"> order (Int): Order (length) of the group</span>
|
||
<span class="sd"> """</span>
|
||
<span class="k">def</span><span class="w"> </span><span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">n</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">):</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_n</span> <span class="o">=</span> <span class="n">n</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_a</span> <span class="o">=</span> <span class="n">a</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_b</span> <span class="o">=</span> <span class="n">b</span>
|
||
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_squares</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">()</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_E</span> <span class="o">=</span> <span class="nb">list</span><span class="p">()</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_order</span> <span class="o">=</span> <span class="mi">0</span>
|
||
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">quadraticResidues</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function generate all quadratic modulo of n.</span>
|
||
<span class="sd"> A quadratic: if exist and satisfy $x^2 \equiv q mod n$, means it's a square modulo n and q is quadratic nonresidue modulo n</span>
|
||
<span class="sd"> https://en.wikipedia.org/wiki/Quadratic_residue</span>
|
||
|
||
<span class="sd"> For instance, n = 13, q = 9</span>
|
||
<span class="sd"> For all x belongs to n</span>
|
||
<span class="sd"> for x in n:</span>
|
||
<span class="sd"> if x ** 2 % n == q:</span>
|
||
<span class="sd"> print(x, q)</span>
|
||
<span class="sd"> """</span>
|
||
<span class="k">for</span> <span class="n">q</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_n</span><span class="p">):</span>
|
||
<span class="n">x2</span> <span class="o">=</span> <span class="nb">pow</span><span class="p">(</span><span class="n">q</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
<span class="k">if</span> <span class="n">x2</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_squares</span><span class="p">:</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_squares</span><span class="p">[</span><span class="n">x2</span><span class="p">]</span> <span class="o">=</span> <span class="nb">list</span><span class="p">()</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_squares</span><span class="p">[</span><span class="n">x2</span><span class="p">]</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">q</span><span class="p">)</span>
|
||
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">getQuadraticResidues</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span> <span class="o">-></span> <span class="nb">dict</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function return the dict contains all squares modulo of n</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return a dictionary of squares modulo</span>
|
||
<span class="sd"> """</span>
|
||
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_squares</span>
|
||
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">pointsE</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function generate all points for $E(F_p)$. Each entry in the list contain another list of two entries: x and y</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return the list of points of E(F_p)</span>
|
||
<span class="sd"> """</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_E</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">Point</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">))</span>
|
||
<span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_n</span><span class="p">):</span>
|
||
<span class="n">y</span> <span class="o">=</span> <span class="p">(</span><span class="nb">pow</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span> <span class="o">+</span> <span class="p">(</span><span class="n">x</span> <span class="o">*</span> <span class="bp">self</span><span class="o">.</span><span class="n">_a</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">_b</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
|
||
<span class="c1"># If not quadratic residue, no point in the curve</span>
|
||
<span class="c1"># and x not produce a point in the curve</span>
|
||
<span class="k">if</span> <span class="n">y</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_squares</span><span class="p">:</span>
|
||
<span class="k">for</span> <span class="n">e</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_squares</span><span class="p">[</span><span class="n">y</span><span class="p">]:</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_E</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">Point</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">e</span><span class="p">))</span>
|
||
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_E</span>
|
||
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">additionTable</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
|
||
<span class="k">raise</span> <span class="ne">NotImplementedError</span>
|
||
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">_slope</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
|
||
<span class="k">raise</span> <span class="ne">NotImplementedError</span>
|
||
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">_curves</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_curves</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">()</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_curves</span><span class="p">[</span><span class="s2">"weierstrass"</span><span class="p">]</span> <span class="o">=</span> <span class="n">weierstrass</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_curves</span><span class="p">[</span><span class="s2">"curve25519"</span><span class="p">]</span> <span class="o">=</span> <span class="n">curve25519</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_curves</span><span class="p">[</span><span class="s2">"curve448"</span><span class="p">]</span> <span class="o">=</span> <span class="n">curve448</span>
|
||
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">weierstrass</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span>
|
||
<span class="k">raise</span> <span class="ne">NotImplementedError</span>
|
||
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">curve448</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span>
|
||
<span class="k">raise</span> <span class="ne">NotImplementedError</span>
|
||
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">curve25519</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function generate a curve based on the Montgomery's curve.</span>
|
||
<span class="sd"> Using that formula: y2 = x^3 + 486662\times x^2 + x</span>
|
||
<span class="sd"> """</span>
|
||
<span class="n">y</span> <span class="o">=</span> <span class="nb">pow</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span> <span class="o">+</span> <span class="mi">486662</span> <span class="o">*</span> <span class="nb">pow</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span> <span class="o">+</span> <span class="n">x</span>
|
||
<span class="k">if</span> <span class="n">y</span> <span class="o">></span> <span class="mi">0</span><span class="p">:</span>
|
||
<span class="k">return</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">y</span><span class="p">)</span>
|
||
<span class="k">else</span><span class="p">:</span>
|
||
<span class="k">return</span> <span class="mi">0</span>
|
||
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">add</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">P</span><span class="p">,</span> <span class="n">Q</span><span class="p">)</span> <span class="o">-></span> <span class="n">Point</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function operathe addition operation on two points P and Q</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> P (Object): The first Point on the curve</span>
|
||
<span class="sd"> Q (Object): The second Point on the curve</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return the Point object R</span>
|
||
<span class="sd"> """</span>
|
||
|
||
<span class="c1">## Check if P or Q are infinity</span>
|
||
<span class="k">if</span> <span class="p">(</span><span class="n">P</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="n">P</span><span class="o">.</span><span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="ow">and</span> <span class="p">(</span><span class="n">Q</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="n">Q</span><span class="o">.</span><span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span>
|
||
<span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
|
||
<span class="k">elif</span> <span class="p">(</span><span class="n">P</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="n">P</span><span class="o">.</span><span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span>
|
||
<span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="n">Q</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="n">Q</span><span class="o">.</span><span class="n">y</span><span class="p">)</span>
|
||
<span class="k">elif</span> <span class="p">(</span><span class="n">Q</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="n">Q</span><span class="o">.</span><span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span>
|
||
<span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="n">P</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="n">P</span><span class="o">.</span><span class="n">y</span><span class="p">)</span>
|
||
|
||
<span class="c1"># point doubling</span>
|
||
<span class="k">if</span> <span class="n">P</span><span class="o">.</span><span class="n">x</span> <span class="o">==</span> <span class="n">Q</span><span class="o">.</span><span class="n">x</span><span class="p">:</span>
|
||
<span class="c1"># Infinity</span>
|
||
<span class="k">if</span> <span class="n">P</span><span class="o">.</span><span class="n">y</span> <span class="o">!=</span> <span class="n">Q</span><span class="o">.</span><span class="n">y</span> <span class="ow">or</span> <span class="n">Q</span><span class="o">.</span><span class="n">y</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
|
||
<span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
|
||
|
||
<span class="c1"># Point doubling</span>
|
||
<span class="k">try</span><span class="p">:</span>
|
||
<span class="n">inv</span> <span class="o">=</span> <span class="nb">pow</span><span class="p">(</span><span class="mi">2</span> <span class="o">*</span> <span class="n">P</span><span class="o">.</span><span class="n">y</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span><span class="p">);</span> <span class="c1"># It's working with the inverse modular, WHY ???</span>
|
||
<span class="n">m</span> <span class="o">=</span> <span class="p">((</span><span class="mi">3</span> <span class="o">*</span> <span class="nb">pow</span><span class="p">(</span><span class="n">P</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="mi">2</span><span class="p">))</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">_a</span><span class="p">)</span> <span class="o">*</span> <span class="n">inv</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
<span class="k">except</span> <span class="ne">ValueError</span><span class="p">:</span>
|
||
<span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
|
||
|
||
<span class="k">else</span><span class="p">:</span>
|
||
<span class="k">try</span><span class="p">:</span>
|
||
<span class="n">inv</span> <span class="o">=</span> <span class="nb">pow</span><span class="p">(</span><span class="n">Q</span><span class="o">.</span><span class="n">x</span> <span class="o">-</span> <span class="n">P</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span><span class="p">)</span>
|
||
<span class="n">m</span> <span class="o">=</span> <span class="p">((</span><span class="n">Q</span><span class="o">.</span><span class="n">y</span> <span class="o">-</span> <span class="n">P</span><span class="o">.</span><span class="n">y</span><span class="p">)</span> <span class="o">*</span> <span class="n">inv</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
<span class="k">except</span> <span class="ne">ValueError</span><span class="p">:</span>
|
||
<span class="c1"># May call this Exception: base is not invertible for the given modulus</span>
|
||
<span class="c1"># I return an Infinity point until I fixed that</span>
|
||
<span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
|
||
|
||
<span class="n">xr</span> <span class="o">=</span> <span class="nb">int</span><span class="p">((</span><span class="nb">pow</span><span class="p">(</span><span class="n">m</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span> <span class="o">-</span> <span class="n">P</span><span class="o">.</span><span class="n">x</span> <span class="o">-</span> <span class="n">Q</span><span class="o">.</span><span class="n">x</span><span class="p">))</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
|
||
<span class="n">yr</span> <span class="o">=</span> <span class="nb">int</span><span class="p">((</span><span class="n">m</span> <span class="o">*</span> <span class="p">(</span><span class="n">P</span><span class="o">.</span><span class="n">x</span> <span class="o">-</span> <span class="n">xr</span><span class="p">))</span> <span class="o">-</span> <span class="n">P</span><span class="o">.</span><span class="n">y</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
<span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="n">xr</span><span class="p">,</span> <span class="n">yr</span><span class="p">)</span>
|
||
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">scalar</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">P</span><span class="p">,</span> <span class="n">n</span><span class="p">)</span> <span class="o">-></span> <span class="n">Point</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function compute a Scalar Multiplication of P, n time. This algorithm is also known as Double and Add.</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> P (point): the Point to multiplication</span>
|
||
<span class="sd"> n (Integer): multiplicate n time P</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return the result of the Scalar multiplication</span>
|
||
<span class="sd"> """</span>
|
||
<span class="n">binary</span> <span class="o">=</span> <span class="nb">bin</span><span class="p">(</span><span class="n">n</span><span class="p">)[</span><span class="mi">2</span><span class="p">:]</span>
|
||
<span class="n">binary</span> <span class="o">=</span> <span class="n">binary</span><span class="p">[::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="c1"># We need to reverse the binary</span>
|
||
|
||
<span class="n">nP</span> <span class="o">=</span> <span class="n">Point</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
|
||
<span class="n">Rtmp</span> <span class="o">=</span> <span class="n">P</span>
|
||
|
||
<span class="k">for</span> <span class="n">b</span> <span class="ow">in</span> <span class="n">binary</span><span class="p">:</span>
|
||
<span class="k">if</span> <span class="n">b</span> <span class="o">==</span> <span class="s1">'1'</span><span class="p">:</span>
|
||
<span class="n">nP</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">nP</span><span class="p">,</span> <span class="n">Rtmp</span><span class="p">)</span>
|
||
<span class="n">Rtmp</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">Rtmp</span><span class="p">,</span> <span class="n">Rtmp</span><span class="p">)</span> <span class="c1"># Double P</span>
|
||
|
||
<span class="k">return</span> <span class="n">nP</span>
|
||
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">pointExist</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">P</span><span class="p">)</span> <span class="o">-></span> <span class="nb">bool</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function determine if the Point P(x, y) exist in the Curve</span>
|
||
<span class="sd"> To identify if a point P (x, y) lies on the curve</span>
|
||
<span class="sd"> We need to compute y ** 2 mod n</span>
|
||
<span class="sd"> Then, we compute x ** 3 + ax + b mod n</span>
|
||
<span class="sd"> If both are equal, the point exist, otherwise not</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> P (Point): The point to check if exist in the curve</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return True if lies on the curve otherwise it's False</span>
|
||
<span class="sd"> """</span>
|
||
<span class="n">y2</span> <span class="o">=</span> <span class="nb">pow</span><span class="p">(</span><span class="n">P</span><span class="o">.</span><span class="n">y</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
<span class="n">x3</span> <span class="o">=</span> <span class="p">(</span><span class="nb">pow</span><span class="p">(</span><span class="n">P</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span> <span class="o">+</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_a</span> <span class="o">*</span> <span class="n">P</span><span class="o">.</span><span class="n">x</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">_b</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
<span class="k">if</span> <span class="n">y2</span> <span class="o">==</span> <span class="n">x3</span><span class="p">:</span>
|
||
<span class="k">return</span> <span class="kc">True</span>
|
||
|
||
<span class="k">return</span> <span class="kc">False</span>
|
||
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">findOrder</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span> <span class="o">-></span> <span class="nb">int</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function find the order of the Curve over Fp</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return the order of the Curve</span>
|
||
<span class="sd"> """</span>
|
||
<span class="n">l</span> <span class="o">=</span> <span class="nb">list</span><span class="p">()</span>
|
||
<span class="n">l</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">Point</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">))</span>
|
||
|
||
<span class="c1"># It's the same of the function pointsE</span>
|
||
<span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_n</span><span class="p">):</span>
|
||
<span class="n">r</span> <span class="o">=</span> <span class="p">(</span><span class="nb">pow</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span> <span class="o">+</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_a</span> <span class="o">*</span> <span class="n">x</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">_b</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
<span class="k">if</span> <span class="n">r</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_squares</span><span class="p">:</span>
|
||
<span class="k">for</span> <span class="n">s</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_squares</span><span class="p">[</span><span class="n">r</span><span class="p">]:</span>
|
||
<span class="n">P</span> <span class="o">=</span> <span class="n">Point</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">s</span><span class="p">)</span>
|
||
<span class="n">l</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">P</span><span class="p">)</span>
|
||
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_order</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">l</span><span class="p">)</span>
|
||
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_order</span>
|
||
|
||
<span class="nd">@property</span>
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">order</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span> <span class="o">-></span> <span class="nb">int</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function return the order of the Group</span>
|
||
<span class="sd"> """</span>
|
||
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_order</span>
|
||
|
||
<span class="nd">@property</span>
|
||
<span class="k">def</span><span class="w"> </span><span class="nf">cofactor</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span> <span class="o">-></span> <span class="nb">int</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function return the cofactor. A cofactor describe the relation between the number of points and the group.</span>
|
||
<span class="sd"> It's based on the Lagrange's theorem.</span>
|
||
<span class="sd"> """</span>
|
||
<span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">_order</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
|
||
<span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s2">"You must generate the order of the group"</span><span class="p">)</span>
|
||
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_order</span> <span class="o">/</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
|
||
|
||
|
||
<div class="doc doc-children">
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
<div class="doc doc-object doc-attribute">
|
||
|
||
|
||
|
||
<h3 id="Cryptotools.Groups.elliptic.Elliptic.cofactor" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">cofactor</span></code>
|
||
|
||
<span class="doc doc-labels">
|
||
<small class="doc doc-label doc-label-property"><code>property</code></small>
|
||
</span>
|
||
|
||
</h3>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function return the cofactor. A cofactor describe the relation between the number of points and the group.
|
||
It's based on the Lagrange's theorem.</p>
|
||
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-attribute">
|
||
|
||
|
||
|
||
<h3 id="Cryptotools.Groups.elliptic.Elliptic.order" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">order</span></code>
|
||
|
||
<span class="doc doc-labels">
|
||
<small class="doc doc-label doc-label-property"><code>property</code></small>
|
||
</span>
|
||
|
||
</h3>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function return the order of the Group</p>
|
||
|
||
</div>
|
||
|
||
</div>
|
||
|
||
|
||
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h3 id="Cryptotools.Groups.elliptic.Elliptic.add" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">add</span><span class="p">(</span><span class="n">P</span><span class="p">,</span> <span class="n">Q</span><span class="p">)</span></code>
|
||
|
||
</h3>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function operathe addition operation on two points P and Q</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Parameters:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<b><code>P</code></b>
|
||
(<code><span title="Object">Object</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>The first Point on the curve</p>
|
||
</div>
|
||
</li>
|
||
<li>
|
||
<b><code>Q</code></b>
|
||
(<code><span title="Object">Object</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>The second Point on the curve</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<code><a class="autorefs autorefs-internal" title="Point (Cryptotools.Groups.point.Point)" href="../curves/#Cryptotools.Groups.point.Point">Point</a></code>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return the Point object R</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="mkdocstrings-source">
|
||
<summary>Source code in <code>Cryptotools/Groups/elliptic.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">111</span>
|
||
<span class="normal">112</span>
|
||
<span class="normal">113</span>
|
||
<span class="normal">114</span>
|
||
<span class="normal">115</span>
|
||
<span class="normal">116</span>
|
||
<span class="normal">117</span>
|
||
<span class="normal">118</span>
|
||
<span class="normal">119</span>
|
||
<span class="normal">120</span>
|
||
<span class="normal">121</span>
|
||
<span class="normal">122</span>
|
||
<span class="normal">123</span>
|
||
<span class="normal">124</span>
|
||
<span class="normal">125</span>
|
||
<span class="normal">126</span>
|
||
<span class="normal">127</span>
|
||
<span class="normal">128</span>
|
||
<span class="normal">129</span>
|
||
<span class="normal">130</span>
|
||
<span class="normal">131</span>
|
||
<span class="normal">132</span>
|
||
<span class="normal">133</span>
|
||
<span class="normal">134</span>
|
||
<span class="normal">135</span>
|
||
<span class="normal">136</span>
|
||
<span class="normal">137</span>
|
||
<span class="normal">138</span>
|
||
<span class="normal">139</span>
|
||
<span class="normal">140</span>
|
||
<span class="normal">141</span>
|
||
<span class="normal">142</span>
|
||
<span class="normal">143</span>
|
||
<span class="normal">144</span>
|
||
<span class="normal">145</span>
|
||
<span class="normal">146</span>
|
||
<span class="normal">147</span>
|
||
<span class="normal">148</span>
|
||
<span class="normal">149</span>
|
||
<span class="normal">150</span>
|
||
<span class="normal">151</span>
|
||
<span class="normal">152</span>
|
||
<span class="normal">153</span>
|
||
<span class="normal">154</span>
|
||
<span class="normal">155</span>
|
||
<span class="normal">156</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span><span class="w"> </span><span class="nf">add</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">P</span><span class="p">,</span> <span class="n">Q</span><span class="p">)</span> <span class="o">-></span> <span class="n">Point</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function operathe addition operation on two points P and Q</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> P (Object): The first Point on the curve</span>
|
||
<span class="sd"> Q (Object): The second Point on the curve</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return the Point object R</span>
|
||
<span class="sd"> """</span>
|
||
|
||
<span class="c1">## Check if P or Q are infinity</span>
|
||
<span class="k">if</span> <span class="p">(</span><span class="n">P</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="n">P</span><span class="o">.</span><span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="ow">and</span> <span class="p">(</span><span class="n">Q</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="n">Q</span><span class="o">.</span><span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span>
|
||
<span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
|
||
<span class="k">elif</span> <span class="p">(</span><span class="n">P</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="n">P</span><span class="o">.</span><span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span>
|
||
<span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="n">Q</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="n">Q</span><span class="o">.</span><span class="n">y</span><span class="p">)</span>
|
||
<span class="k">elif</span> <span class="p">(</span><span class="n">Q</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="n">Q</span><span class="o">.</span><span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span>
|
||
<span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="n">P</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="n">P</span><span class="o">.</span><span class="n">y</span><span class="p">)</span>
|
||
|
||
<span class="c1"># point doubling</span>
|
||
<span class="k">if</span> <span class="n">P</span><span class="o">.</span><span class="n">x</span> <span class="o">==</span> <span class="n">Q</span><span class="o">.</span><span class="n">x</span><span class="p">:</span>
|
||
<span class="c1"># Infinity</span>
|
||
<span class="k">if</span> <span class="n">P</span><span class="o">.</span><span class="n">y</span> <span class="o">!=</span> <span class="n">Q</span><span class="o">.</span><span class="n">y</span> <span class="ow">or</span> <span class="n">Q</span><span class="o">.</span><span class="n">y</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
|
||
<span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
|
||
|
||
<span class="c1"># Point doubling</span>
|
||
<span class="k">try</span><span class="p">:</span>
|
||
<span class="n">inv</span> <span class="o">=</span> <span class="nb">pow</span><span class="p">(</span><span class="mi">2</span> <span class="o">*</span> <span class="n">P</span><span class="o">.</span><span class="n">y</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span><span class="p">);</span> <span class="c1"># It's working with the inverse modular, WHY ???</span>
|
||
<span class="n">m</span> <span class="o">=</span> <span class="p">((</span><span class="mi">3</span> <span class="o">*</span> <span class="nb">pow</span><span class="p">(</span><span class="n">P</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="mi">2</span><span class="p">))</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">_a</span><span class="p">)</span> <span class="o">*</span> <span class="n">inv</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
<span class="k">except</span> <span class="ne">ValueError</span><span class="p">:</span>
|
||
<span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
|
||
|
||
<span class="k">else</span><span class="p">:</span>
|
||
<span class="k">try</span><span class="p">:</span>
|
||
<span class="n">inv</span> <span class="o">=</span> <span class="nb">pow</span><span class="p">(</span><span class="n">Q</span><span class="o">.</span><span class="n">x</span> <span class="o">-</span> <span class="n">P</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span><span class="p">)</span>
|
||
<span class="n">m</span> <span class="o">=</span> <span class="p">((</span><span class="n">Q</span><span class="o">.</span><span class="n">y</span> <span class="o">-</span> <span class="n">P</span><span class="o">.</span><span class="n">y</span><span class="p">)</span> <span class="o">*</span> <span class="n">inv</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
<span class="k">except</span> <span class="ne">ValueError</span><span class="p">:</span>
|
||
<span class="c1"># May call this Exception: base is not invertible for the given modulus</span>
|
||
<span class="c1"># I return an Infinity point until I fixed that</span>
|
||
<span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
|
||
|
||
<span class="n">xr</span> <span class="o">=</span> <span class="nb">int</span><span class="p">((</span><span class="nb">pow</span><span class="p">(</span><span class="n">m</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span> <span class="o">-</span> <span class="n">P</span><span class="o">.</span><span class="n">x</span> <span class="o">-</span> <span class="n">Q</span><span class="o">.</span><span class="n">x</span><span class="p">))</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
|
||
<span class="n">yr</span> <span class="o">=</span> <span class="nb">int</span><span class="p">((</span><span class="n">m</span> <span class="o">*</span> <span class="p">(</span><span class="n">P</span><span class="o">.</span><span class="n">x</span> <span class="o">-</span> <span class="n">xr</span><span class="p">))</span> <span class="o">-</span> <span class="n">P</span><span class="o">.</span><span class="n">y</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
<span class="k">return</span> <span class="n">Point</span><span class="p">(</span><span class="n">xr</span><span class="p">,</span> <span class="n">yr</span><span class="p">)</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h3 id="Cryptotools.Groups.elliptic.Elliptic.curve25519" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">curve25519</span><span class="p">(</span><span class="n">x</span><span class="p">)</span></code>
|
||
|
||
</h3>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function generate a curve based on the Montgomery's curve.
|
||
Using that formula: y2 = x^3 + 486662 imes x^2 + x</p>
|
||
|
||
|
||
<details class="mkdocstrings-source">
|
||
<summary>Source code in <code>Cryptotools/Groups/elliptic.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">100</span>
|
||
<span class="normal">101</span>
|
||
<span class="normal">102</span>
|
||
<span class="normal">103</span>
|
||
<span class="normal">104</span>
|
||
<span class="normal">105</span>
|
||
<span class="normal">106</span>
|
||
<span class="normal">107</span>
|
||
<span class="normal">108</span>
|
||
<span class="normal">109</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span><span class="w"> </span><span class="nf">curve25519</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function generate a curve based on the Montgomery's curve.</span>
|
||
<span class="sd"> Using that formula: y2 = x^3 + 486662\times x^2 + x</span>
|
||
<span class="sd"> """</span>
|
||
<span class="n">y</span> <span class="o">=</span> <span class="nb">pow</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span> <span class="o">+</span> <span class="mi">486662</span> <span class="o">*</span> <span class="nb">pow</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span> <span class="o">+</span> <span class="n">x</span>
|
||
<span class="k">if</span> <span class="n">y</span> <span class="o">></span> <span class="mi">0</span><span class="p">:</span>
|
||
<span class="k">return</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">y</span><span class="p">)</span>
|
||
<span class="k">else</span><span class="p">:</span>
|
||
<span class="k">return</span> <span class="mi">0</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h3 id="Cryptotools.Groups.elliptic.Elliptic.findOrder" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">findOrder</span><span class="p">()</span></code>
|
||
|
||
</h3>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function find the order of the Curve over Fp</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<code><span title="int">int</span></code>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return the order of the Curve</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="mkdocstrings-source">
|
||
<summary>Source code in <code>Cryptotools/Groups/elliptic.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">203</span>
|
||
<span class="normal">204</span>
|
||
<span class="normal">205</span>
|
||
<span class="normal">206</span>
|
||
<span class="normal">207</span>
|
||
<span class="normal">208</span>
|
||
<span class="normal">209</span>
|
||
<span class="normal">210</span>
|
||
<span class="normal">211</span>
|
||
<span class="normal">212</span>
|
||
<span class="normal">213</span>
|
||
<span class="normal">214</span>
|
||
<span class="normal">215</span>
|
||
<span class="normal">216</span>
|
||
<span class="normal">217</span>
|
||
<span class="normal">218</span>
|
||
<span class="normal">219</span>
|
||
<span class="normal">220</span>
|
||
<span class="normal">221</span>
|
||
<span class="normal">222</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span><span class="w"> </span><span class="nf">findOrder</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span> <span class="o">-></span> <span class="nb">int</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function find the order of the Curve over Fp</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return the order of the Curve</span>
|
||
<span class="sd"> """</span>
|
||
<span class="n">l</span> <span class="o">=</span> <span class="nb">list</span><span class="p">()</span>
|
||
<span class="n">l</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">Point</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">))</span>
|
||
|
||
<span class="c1"># It's the same of the function pointsE</span>
|
||
<span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_n</span><span class="p">):</span>
|
||
<span class="n">r</span> <span class="o">=</span> <span class="p">(</span><span class="nb">pow</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span> <span class="o">+</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_a</span> <span class="o">*</span> <span class="n">x</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">_b</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
<span class="k">if</span> <span class="n">r</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_squares</span><span class="p">:</span>
|
||
<span class="k">for</span> <span class="n">s</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_squares</span><span class="p">[</span><span class="n">r</span><span class="p">]:</span>
|
||
<span class="n">P</span> <span class="o">=</span> <span class="n">Point</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">s</span><span class="p">)</span>
|
||
<span class="n">l</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">P</span><span class="p">)</span>
|
||
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_order</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">l</span><span class="p">)</span>
|
||
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_order</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h3 id="Cryptotools.Groups.elliptic.Elliptic.getQuadraticResidues" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">getQuadraticResidues</span><span class="p">()</span></code>
|
||
|
||
</h3>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function return the dict contains all squares modulo of n</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<code><span title="dict">dict</span></code>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return a dictionary of squares modulo</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="mkdocstrings-source">
|
||
<summary>Source code in <code>Cryptotools/Groups/elliptic.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">55</span>
|
||
<span class="normal">56</span>
|
||
<span class="normal">57</span>
|
||
<span class="normal">58</span>
|
||
<span class="normal">59</span>
|
||
<span class="normal">60</span>
|
||
<span class="normal">61</span>
|
||
<span class="normal">62</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span><span class="w"> </span><span class="nf">getQuadraticResidues</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span> <span class="o">-></span> <span class="nb">dict</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function return the dict contains all squares modulo of n</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return a dictionary of squares modulo</span>
|
||
<span class="sd"> """</span>
|
||
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_squares</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h3 id="Cryptotools.Groups.elliptic.Elliptic.pointExist" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">pointExist</span><span class="p">(</span><span class="n">P</span><span class="p">)</span></code>
|
||
|
||
</h3>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function determine if the Point P(x, y) exist in the Curve
|
||
To identify if a point P (x, y) lies on the curve
|
||
We need to compute y ** 2 mod n
|
||
Then, we compute x ** 3 + ax + b mod n
|
||
If both are equal, the point exist, otherwise not</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Parameters:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<b><code>P</code></b>
|
||
(<code><a class="autorefs autorefs-internal" title="Point (Cryptotools.Groups.point.Point)" href="../curves/#Cryptotools.Groups.point.Point">Point</a></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>The point to check if exist in the curve</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<code><span title="bool">bool</span></code>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return True if lies on the curve otherwise it's False</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="mkdocstrings-source">
|
||
<summary>Source code in <code>Cryptotools/Groups/elliptic.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">182</span>
|
||
<span class="normal">183</span>
|
||
<span class="normal">184</span>
|
||
<span class="normal">185</span>
|
||
<span class="normal">186</span>
|
||
<span class="normal">187</span>
|
||
<span class="normal">188</span>
|
||
<span class="normal">189</span>
|
||
<span class="normal">190</span>
|
||
<span class="normal">191</span>
|
||
<span class="normal">192</span>
|
||
<span class="normal">193</span>
|
||
<span class="normal">194</span>
|
||
<span class="normal">195</span>
|
||
<span class="normal">196</span>
|
||
<span class="normal">197</span>
|
||
<span class="normal">198</span>
|
||
<span class="normal">199</span>
|
||
<span class="normal">200</span>
|
||
<span class="normal">201</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span><span class="w"> </span><span class="nf">pointExist</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">P</span><span class="p">)</span> <span class="o">-></span> <span class="nb">bool</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function determine if the Point P(x, y) exist in the Curve</span>
|
||
<span class="sd"> To identify if a point P (x, y) lies on the curve</span>
|
||
<span class="sd"> We need to compute y ** 2 mod n</span>
|
||
<span class="sd"> Then, we compute x ** 3 + ax + b mod n</span>
|
||
<span class="sd"> If both are equal, the point exist, otherwise not</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> P (Point): The point to check if exist in the curve</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return True if lies on the curve otherwise it's False</span>
|
||
<span class="sd"> """</span>
|
||
<span class="n">y2</span> <span class="o">=</span> <span class="nb">pow</span><span class="p">(</span><span class="n">P</span><span class="o">.</span><span class="n">y</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
<span class="n">x3</span> <span class="o">=</span> <span class="p">(</span><span class="nb">pow</span><span class="p">(</span><span class="n">P</span><span class="o">.</span><span class="n">x</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span> <span class="o">+</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_a</span> <span class="o">*</span> <span class="n">P</span><span class="o">.</span><span class="n">x</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">_b</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
<span class="k">if</span> <span class="n">y2</span> <span class="o">==</span> <span class="n">x3</span><span class="p">:</span>
|
||
<span class="k">return</span> <span class="kc">True</span>
|
||
|
||
<span class="k">return</span> <span class="kc">False</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h3 id="Cryptotools.Groups.elliptic.Elliptic.pointsE" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">pointsE</span><span class="p">()</span></code>
|
||
|
||
</h3>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function generate all points for $E(F_p)$. Each entry in the list contain another list of two entries: x and y</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return the list of points of E(F_p)</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="mkdocstrings-source">
|
||
<summary>Source code in <code>Cryptotools/Groups/elliptic.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">64</span>
|
||
<span class="normal">65</span>
|
||
<span class="normal">66</span>
|
||
<span class="normal">67</span>
|
||
<span class="normal">68</span>
|
||
<span class="normal">69</span>
|
||
<span class="normal">70</span>
|
||
<span class="normal">71</span>
|
||
<span class="normal">72</span>
|
||
<span class="normal">73</span>
|
||
<span class="normal">74</span>
|
||
<span class="normal">75</span>
|
||
<span class="normal">76</span>
|
||
<span class="normal">77</span>
|
||
<span class="normal">78</span>
|
||
<span class="normal">79</span>
|
||
<span class="normal">80</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span><span class="w"> </span><span class="nf">pointsE</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function generate all points for $E(F_p)$. Each entry in the list contain another list of two entries: x and y</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return the list of points of E(F_p)</span>
|
||
<span class="sd"> """</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_E</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">Point</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">))</span>
|
||
<span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_n</span><span class="p">):</span>
|
||
<span class="n">y</span> <span class="o">=</span> <span class="p">(</span><span class="nb">pow</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span> <span class="o">+</span> <span class="p">(</span><span class="n">x</span> <span class="o">*</span> <span class="bp">self</span><span class="o">.</span><span class="n">_a</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">_b</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
|
||
<span class="c1"># If not quadratic residue, no point in the curve</span>
|
||
<span class="c1"># and x not produce a point in the curve</span>
|
||
<span class="k">if</span> <span class="n">y</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_squares</span><span class="p">:</span>
|
||
<span class="k">for</span> <span class="n">e</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_squares</span><span class="p">[</span><span class="n">y</span><span class="p">]:</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_E</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">Point</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">e</span><span class="p">))</span>
|
||
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_E</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h3 id="Cryptotools.Groups.elliptic.Elliptic.quadraticResidues" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">quadraticResidues</span><span class="p">()</span></code>
|
||
|
||
</h3>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function generate all quadratic modulo of n.
|
||
A quadratic: if exist and satisfy $x^2 \equiv q mod n$, means it's a square modulo n and q is quadratic nonresidue modulo n
|
||
https://en.wikipedia.org/wiki/Quadratic_residue</p>
|
||
<p>For instance, n = 13, q = 9
|
||
For all x belongs to n
|
||
for x in n:
|
||
if x ** 2 % n == q:
|
||
print(x, q)</p>
|
||
|
||
|
||
<details class="mkdocstrings-source">
|
||
<summary>Source code in <code>Cryptotools/Groups/elliptic.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">37</span>
|
||
<span class="normal">38</span>
|
||
<span class="normal">39</span>
|
||
<span class="normal">40</span>
|
||
<span class="normal">41</span>
|
||
<span class="normal">42</span>
|
||
<span class="normal">43</span>
|
||
<span class="normal">44</span>
|
||
<span class="normal">45</span>
|
||
<span class="normal">46</span>
|
||
<span class="normal">47</span>
|
||
<span class="normal">48</span>
|
||
<span class="normal">49</span>
|
||
<span class="normal">50</span>
|
||
<span class="normal">51</span>
|
||
<span class="normal">52</span>
|
||
<span class="normal">53</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span><span class="w"> </span><span class="nf">quadraticResidues</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function generate all quadratic modulo of n.</span>
|
||
<span class="sd"> A quadratic: if exist and satisfy $x^2 \equiv q mod n$, means it's a square modulo n and q is quadratic nonresidue modulo n</span>
|
||
<span class="sd"> https://en.wikipedia.org/wiki/Quadratic_residue</span>
|
||
|
||
<span class="sd"> For instance, n = 13, q = 9</span>
|
||
<span class="sd"> For all x belongs to n</span>
|
||
<span class="sd"> for x in n:</span>
|
||
<span class="sd"> if x ** 2 % n == q:</span>
|
||
<span class="sd"> print(x, q)</span>
|
||
<span class="sd"> """</span>
|
||
<span class="k">for</span> <span class="n">q</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_n</span><span class="p">):</span>
|
||
<span class="n">x2</span> <span class="o">=</span> <span class="nb">pow</span><span class="p">(</span><span class="n">q</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="o">.</span><span class="n">_n</span>
|
||
<span class="k">if</span> <span class="n">x2</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_squares</span><span class="p">:</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_squares</span><span class="p">[</span><span class="n">x2</span><span class="p">]</span> <span class="o">=</span> <span class="nb">list</span><span class="p">()</span>
|
||
<span class="bp">self</span><span class="o">.</span><span class="n">_squares</span><span class="p">[</span><span class="n">x2</span><span class="p">]</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">q</span><span class="p">)</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<div class="doc doc-object doc-function">
|
||
|
||
|
||
<h3 id="Cryptotools.Groups.elliptic.Elliptic.scalar" class="doc doc-heading">
|
||
<code class="highlight language-python"><span class="n">scalar</span><span class="p">(</span><span class="n">P</span><span class="p">,</span> <span class="n">n</span><span class="p">)</span></code>
|
||
|
||
</h3>
|
||
|
||
|
||
<div class="doc doc-contents ">
|
||
|
||
<p>This function compute a Scalar Multiplication of P, n time. This algorithm is also known as Double and Add.</p>
|
||
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Parameters:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<b><code>P</code></b>
|
||
(<code><a class="autorefs autorefs-internal" title="Cryptotools.Groups.point" href="../curves/#Cryptotools.Groups.point">point</a></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>the Point to multiplication</p>
|
||
</div>
|
||
</li>
|
||
<li>
|
||
<b><code>n</code></b>
|
||
(<code><span title="Integer">Integer</span></code>)
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>multiplicate n time P</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<table class="field-list">
|
||
<colgroup>
|
||
<col class="field-name" />
|
||
<col class="field-body" />
|
||
</colgroup>
|
||
<tbody valign="top">
|
||
<tr class="field">
|
||
<th class="field-name">Returns:</th>
|
||
<td class="field-body">
|
||
<ul class="first simple">
|
||
<li>
|
||
<code><a class="autorefs autorefs-internal" title="Point (Cryptotools.Groups.point.Point)" href="../curves/#Cryptotools.Groups.point.Point">Point</a></code>
|
||
–
|
||
<div class="doc-md-description">
|
||
<p>Return the result of the Scalar multiplication</p>
|
||
</div>
|
||
</li>
|
||
</ul>
|
||
</td>
|
||
</tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<details class="mkdocstrings-source">
|
||
<summary>Source code in <code>Cryptotools/Groups/elliptic.py</code></summary>
|
||
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">158</span>
|
||
<span class="normal">159</span>
|
||
<span class="normal">160</span>
|
||
<span class="normal">161</span>
|
||
<span class="normal">162</span>
|
||
<span class="normal">163</span>
|
||
<span class="normal">164</span>
|
||
<span class="normal">165</span>
|
||
<span class="normal">166</span>
|
||
<span class="normal">167</span>
|
||
<span class="normal">168</span>
|
||
<span class="normal">169</span>
|
||
<span class="normal">170</span>
|
||
<span class="normal">171</span>
|
||
<span class="normal">172</span>
|
||
<span class="normal">173</span>
|
||
<span class="normal">174</span>
|
||
<span class="normal">175</span>
|
||
<span class="normal">176</span>
|
||
<span class="normal">177</span>
|
||
<span class="normal">178</span>
|
||
<span class="normal">179</span>
|
||
<span class="normal">180</span></pre></div></td><td class="code"><div><pre><span></span><code><span class="k">def</span><span class="w"> </span><span class="nf">scalar</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">P</span><span class="p">,</span> <span class="n">n</span><span class="p">)</span> <span class="o">-></span> <span class="n">Point</span><span class="p">:</span>
|
||
<span class="w"> </span><span class="sd">"""</span>
|
||
<span class="sd"> This function compute a Scalar Multiplication of P, n time. This algorithm is also known as Double and Add.</span>
|
||
|
||
<span class="sd"> Args:</span>
|
||
<span class="sd"> P (point): the Point to multiplication</span>
|
||
<span class="sd"> n (Integer): multiplicate n time P</span>
|
||
|
||
<span class="sd"> Returns:</span>
|
||
<span class="sd"> Return the result of the Scalar multiplication</span>
|
||
<span class="sd"> """</span>
|
||
<span class="n">binary</span> <span class="o">=</span> <span class="nb">bin</span><span class="p">(</span><span class="n">n</span><span class="p">)[</span><span class="mi">2</span><span class="p">:]</span>
|
||
<span class="n">binary</span> <span class="o">=</span> <span class="n">binary</span><span class="p">[::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="c1"># We need to reverse the binary</span>
|
||
|
||
<span class="n">nP</span> <span class="o">=</span> <span class="n">Point</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
|
||
<span class="n">Rtmp</span> <span class="o">=</span> <span class="n">P</span>
|
||
|
||
<span class="k">for</span> <span class="n">b</span> <span class="ow">in</span> <span class="n">binary</span><span class="p">:</span>
|
||
<span class="k">if</span> <span class="n">b</span> <span class="o">==</span> <span class="s1">'1'</span><span class="p">:</span>
|
||
<span class="n">nP</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">nP</span><span class="p">,</span> <span class="n">Rtmp</span><span class="p">)</span>
|
||
<span class="n">Rtmp</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">Rtmp</span><span class="p">,</span> <span class="n">Rtmp</span><span class="p">)</span> <span class="c1"># Double P</span>
|
||
|
||
<span class="k">return</span> <span class="n">nP</span>
|
||
</code></pre></div></td></tr></table></div>
|
||
</details>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
|
||
|
||
</div>
|
||
|
||
</div>
|
||
|
||
|
||
</div>
|
||
|
||
|
||
|
||
|
||
</div>
|
||
|
||
</div>
|
||
|
||
</div>
|
||
|
||
</div>
|
||
</div><footer>
|
||
<div class="rst-footer-buttons" role="navigation" aria-label="Footer Navigation">
|
||
<a href="../curves/" class="btn btn-neutral float-left" title="Curves"><span class="icon icon-circle-arrow-left"></span> Previous</a>
|
||
<a href="../rsa/" class="btn btn-neutral float-right" title="RSA">Next <span class="icon icon-circle-arrow-right"></span></a>
|
||
</div>
|
||
|
||
<hr/>
|
||
|
||
<div role="contentinfo">
|
||
<!-- Copyright etc -->
|
||
</div>
|
||
|
||
Built with <a href="https://www.mkdocs.org/">MkDocs</a> using a <a href="https://github.com/readthedocs/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>.
|
||
</footer>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
</section>
|
||
|
||
</div>
|
||
|
||
<div class="rst-versions" role="note" aria-label="Versions">
|
||
<span class="rst-current-version" data-toggle="rst-current-version">
|
||
|
||
|
||
<span><a href="../curves/" style="color: #fcfcfc">« Previous</a></span>
|
||
|
||
|
||
<span><a href="../rsa/" style="color: #fcfcfc">Next »</a></span>
|
||
|
||
</span>
|
||
</div>
|
||
<script src="../js/jquery-3.6.0.min.js"></script>
|
||
<script>var base_url = "..";</script>
|
||
<script src="../js/theme_extra.js"></script>
|
||
<script src="../js/theme.js"></script>
|
||
<script>
|
||
jQuery(function () {
|
||
SphinxRtdTheme.Navigation.enable(true);
|
||
});
|
||
</script>
|
||
|
||
</body>
|
||
</html>
|