{"action":"created","comment":{"url":"https://api.github.com/repos/keep-network/paillier/pulls/comments/205783549","pull_request_review_id":141074412,"id":205783549,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDIwNTc4MzU0OQ==","diff_hunk":"@@ -0,0 +1,98 @@\n+package paillier\n+\n+import (\n+\t\"errors\"\n+\t\"fmt\"\n+\t\"math/big\"\n+\t\"reflect\"\n+\t\"testing\"\n+\t\"time\"\n+)\n+\n+func TestAsyncGenerator(t *testing.T) {\n+\tconcurrencyLevel := 4\n+\n+\tvar tests = map[string]struct {\n+\t\tbitLen        int\n+\t\ttimeout       time.Duration\n+\t\texpectedError error\n+\t}{\n+\t\t\"primes successfully generated\": {\n+\t\t\tbitLen:        512,\n+\t\t\ttimeout:       60 * time.Second,\n+\t\t\texpectedError: nil,\n+\t\t},\n+\t\t\"generator timed out\": {\n+\t\t\tbitLen:        8192,\n+\t\t\ttimeout:       1 * time.Second,\n+\t\t\texpectedError: errors.New(\"generator timed out after 1s\"),\n+\t\t},\n+\t\t\"bit length is 5\": {\n+\t\t\tbitLen:        5,\n+\t\t\ttimeout:       1 * time.Second,\n+\t\t\texpectedError: errors.New(\"safe prime size must be at least 6 bits\"),\n+\t\t},\n+\t\t\"bit length is 6\": {\n+\t\t\tbitLen:        6,\n+\t\t\ttimeout:       60 * time.Second,\n+\t\t\texpectedError: nil,\n+\t\t},\n+\t}\n+\n+\tfor testName, test := range tests {\n+\t\tt.Run(testName, func(t *testing.T) {\n+\t\t\tp, q, err := GenerateSafePrime(\n+\t\t\t\ttest.bitLen,\n+\t\t\t\tconcurrencyLevel,\n+\t\t\t\ttest.timeout,\n+\t\t\t)\n+\n+\t\t\tif test.expectedError != nil {\n+\t\t\t\tif !reflect.DeepEqual(test.expectedError, err) {\n+\t\t\t\t\tt.Fatalf(\n+\t\t\t\t\t\t\"Unexpected error\\nActual: %v\\nExpected: %v\",\n+\t\t\t\t\t\terr,\n+\t\t\t\t\t\ttest.expectedError,\n+\t\t\t\t\t)\n+\t\t\t\t}\n+\t\t\t} else {\n+\t\t\t\tif err != nil {\n+\t\t\t\t\tt.Fatal(err)\n+\t\t\t\t}\n+\n+\t\t\t\tif !p.ProbablyPrime(20) {\n+\t\t\t\t\tt.Errorf(\"p is not prime; p = %v\", p)\n+\t\t\t\t}\n+\n+\t\t\t\tif !q.ProbablyPrime(20) {\n+\t\t\t\t\tt.Errorf(\"q is not prime; q = %v\", q)\n+\t\t\t\t}\n+\n+\t\t\t\t// p = 2q + 1 ?\n+\t\t\t\texpectedP := new(big.Int)\n+\t\t\t\texpectedP.Mul(big.NewInt(2), q)\n+\t\t\t\texpectedP.Add(expectedP, big.NewInt(1))\n+\n+\t\t\t\tif expectedP.Cmp(p) != 0 {\n+\t\t\t\t\tt.Errorf(\"2q + 1 != p\")\n+\t\t\t\t}\n+\n+\t\t\t\tif len(p.Bytes()) != test.bitLen {","path":"safe_prime_generator_test.go","position":80,"original_position":80,"commit_id":"7ab24f06419078cd13d4886aae5628f0f3f15d0d","original_commit_id":"7ab24f06419078cd13d4886aae5628f0f3f15d0d","user":{"login":"nkuba","id":10741774,"node_id":"MDQ6VXNlcjEwNzQxNzc0","avatar_url":"https://avatars2.githubusercontent.com/u/10741774?v=4","gravatar_id":"","url":"https://api.github.com/users/nkuba","html_url":"https://github.com/nkuba","followers_url":"https://api.github.com/users/nkuba/followers","following_url":"https://api.github.com/users/nkuba/following{/other_user}","gists_url":"https://api.github.com/users/nkuba/gists{/gist_id}","starred_url":"https://api.github.com/users/nkuba/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nkuba/subscriptions","organizations_url":"https://api.github.com/users/nkuba/orgs","repos_url":"https://api.github.com/users/nkuba/repos","events_url":"https://api.github.com/users/nkuba/events{/privacy}","received_events_url":"https://api.github.com/users/nkuba/received_events","type":"User","site_admin":false},"body":"It ain't gonna work","created_at":"2018-07-27T14:03:09Z","updated_at":"2018-07-27T14:14:47Z","html_url":"https://github.com/keep-network/paillier/pull/8#discussion_r205783549","pull_request_url":"https://api.github.com/repos/keep-network/paillier/pulls/8","author_association":"NONE","_links":{"self":{"href":"https://api.github.com/repos/keep-network/paillier/pulls/comments/205783549"},"html":{"href":"https://github.com/keep-network/paillier/pull/8#discussion_r205783549"},"pull_request":{"href":"https://api.github.com/repos/keep-network/paillier/pulls/8"}}},"pull_request":{"url":"https://api.github.com/repos/keep-network/paillier/pulls/8","id":204083828,"node_id":"MDExOlB1bGxSZXF1ZXN0MjA0MDgzODI4","html_url":"https://github.com/keep-network/paillier/pull/8","diff_url":"https://github.com/keep-network/paillier/pull/8.diff","patch_url":"https://github.com/keep-network/paillier/pull/8.patch","issue_url":"https://api.github.com/repos/keep-network/paillier/issues/8","number":8,"state":"open","locked":false,"title":"Improved performance of the safe prime generator","user":{"login":"pdyraga","id":4712360,"node_id":"MDQ6VXNlcjQ3MTIzNjA=","avatar_url":"https://avatars2.githubusercontent.com/u/4712360?v=4","gravatar_id":"","url":"https://api.github.com/users/pdyraga","html_url":"https://github.com/pdyraga","followers_url":"https://api.github.com/users/pdyraga/followers","following_url":"https://api.github.com/users/pdyraga/following{/other_user}","gists_url":"https://api.github.com/users/pdyraga/gists{/gist_id}","starred_url":"https://api.github.com/users/pdyraga/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pdyraga/subscriptions","organizations_url":"https://api.github.com/users/pdyraga/orgs","repos_url":"https://api.github.com/users/pdyraga/repos","events_url":"https://api.github.com/users/pdyraga/events{/privacy}","received_events_url":"https://api.github.com/users/pdyraga/received_events","type":"User","site_admin":false},"body":"Refs https://github.com/keep-network/keep-core/issues/115\r\n\r\nIn order to generate a threshold Paillier key, we need to generate two safe primes `p` and `q`. For our use cases, `p` and `q` must be at least-1024 bit numbers.\r\n\r\nThis PR aims at improving performance of the safe prime generator. The previous approach was as follows:\r\n```\r\n1. Generate prime `q` of `nBits - 1`\r\n2. Compute `p = 2q + 1`.\r\n3. Check if `p` is prime. If it is, return `(p,q)`. If not, go back to the point 1.\r\n```\r\n\r\nThis approach was simple, but not fast enough. In this PR, we propose an alternative algorithm as well as make the search process concurrent.\r\n\r\nThe new algorithm is as follows:\r\n```\r\n1. Generate a random odd number `q` of length `pBitLen-1` with two the most\r\n   significant bytes set to `1`.\r\n2. Execute preliminary primality test on `q` checking whether it is coprime\r\n   to all the elements of `smallPrimes`. It allows to eliminate trivial\r\n   cases quickly, when `q` is obviously no prime, without running an\r\n   expensive final primality tests.\r\n   If `q` is coprime to all of the `smallPrimes`, then go to the point 3.\r\n   If not, add `2` and try again. Do it at most 10 times.\r\n3. Check the potentially prime `q`, whether `q = 1 (mod 3)`. This will\r\n   happen for 50% of cases.\r\n   If it is, then `p = 2q+1` will be a multiple of 3, so it will be obviously\r\n   not a prime number. In this case, add `2` and try again. Do it at most 10\r\n   times. If `q != 1 (mod 3)`, go to the point 4.\r\n4. Now we know `q` is potentially prime and `p = 2q+1` is not a multiple of\r\n   3. We execute a preliminary primality test on `p`, checking whether\r\n   it is coprime to all the elements of `smallPrimes` just like we did for\r\n   `q` in point 2. If `p` is not coprime to at least one element of the\r\n   `smallPrimes`, then go back to point 1.\r\n   If `p` is coprime to all the elements of `smallPrimes`, go to point 5.\r\n5. At this point, we know `q` is potentially prime, and `p=q+1` is also\r\n   potentially prime. We need to execute a final primality test for `q`.\r\n   We apply Miller-Rabin and Baillie-PSW tests. If they succeed, it means\r\n   that `q` is prime with a very high probability. Knowing `q` is prime,\r\n   we use Pocklington's criterion to prove the primality of `p=2q+1`, that\r\n   is, we execute Fermat primality test to base 2 checking whether\r\n   `2^{p-1} = 1 (mod p)`. It's significantly faster than running full\r\n   Miller-Rabin and Baillie-PSW for `p`.\r\n   If `q` and `p` are found to be prime, return them as a result. If not, go\r\n   back to the point 1.\r\n```\r\n\r\nHow fast we generate a prime number is mostly a matter of luck and it depends on how lucky we are with choosing the first bytes. With today's multicore processors, we can execute the process on multiple cores concurrently, accept the first valid result and cancel the rest of work. This way, with the same finding algorithm, we can get the result faster. Such an approach is presented in this PR.\r\n\r\nDetailed benchmark results are presented in the comment. We can observe an improvement in almost all cases (still, a small factor of luck is needed). I've tested for `512`, `1024` and `2048` bit numbers on my MBP 3,1 GHz Intel Core i7 with concurrency level set to 4. \r\nI did not present a result for `2048` bits, since the previous algorithm wasn't able to produce one `2048`bit safe prime in one hour so I had nothing to compare.\r\n\r\nIf you want, you can compare the new approach with the performance of `openssl dhparam -5 2048`. (512/1024). \r\n","created_at":"2018-07-26T09:39:32Z","updated_at":"2018-07-27T14:14:47Z","closed_at":null,"merged_at":null,"merge_commit_sha":"0b5f71610fd88d5a59fe5665fe5ac1e6570b58f5","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[],"milestone":null,"commits_url":"https://api.github.com/repos/keep-network/paillier/pulls/8/commits","review_comments_url":"https://api.github.com/repos/keep-network/paillier/pulls/8/comments","review_comment_url":"https://api.github.com/repos/keep-network/paillier/pulls/comments{/number}","comments_url":"https://api.github.com/repos/keep-network/paillier/issues/8/comments","statuses_url":"https://api.github.com/repos/keep-network/paillier/statuses/7ab24f06419078cd13d4886aae5628f0f3f15d0d","head":{"label":"keep-network:safe-primes-gen","ref":"safe-primes-gen","sha":"7ab24f06419078cd13d4886aae5628f0f3f15d0d","user":{"login":"keep-network","id":30537626,"node_id":"MDEyOk9yZ2FuaXphdGlvbjMwNTM3NjI2","avatar_url":"https://avatars1.githubusercontent.com/u/30537626?v=4","gravatar_id":"","url":"https://api.github.com/users/keep-network","html_url":"https://github.com/keep-network","followers_url":"https://api.github.com/users/keep-network/followers","following_url":"https://api.github.com/users/keep-network/following{/other_user}","gists_url":"https://api.github.com/users/keep-network/gists{/gist_id}","starred_url":"https://api.github.com/users/keep-network/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/keep-network/subscriptions","organizations_url":"https://api.github.com/users/keep-network/orgs","repos_url":"https://api.github.com/users/keep-network/repos","events_url":"https://api.github.com/users/keep-network/events{/privacy}","received_events_url":"https://api.github.com/users/keep-network/received_events","type":"Organization","site_admin":false},"repo":{"id":127683627,"node_id":"MDEwOlJlcG9zaXRvcnkxMjc2ODM2Mjc=","name":"paillier","full_name":"keep-network/paillier","owner":{"login":"keep-network","id":30537626,"node_id":"MDEyOk9yZ2FuaXphdGlvbjMwNTM3NjI2","avatar_url":"https://avatars1.githubusercontent.com/u/30537626?v=4","gravatar_id":"","url":"https://api.github.com/users/keep-network","html_url":"https://github.com/keep-network","followers_url":"https://api.github.com/users/keep-network/followers","following_url":"https://api.github.com/users/keep-network/following{/other_user}","gists_url":"https://api.github.com/users/keep-network/gists{/gist_id}","starred_url":"https://api.github.com/users/keep-network/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/keep-network/subscriptions","organizations_url":"https://api.github.com/users/keep-network/orgs","repos_url":"https://api.github.com/users/keep-network/repos","events_url":"https://api.github.com/users/keep-network/events{/privacy}","received_events_url":"https://api.github.com/users/keep-network/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/keep-network/paillier","description":"Paillier cryptosystem implemented in Go","fork":true,"url":"https://api.github.com/repos/keep-network/paillier","forks_url":"https://api.github.com/repos/keep-network/paillier/forks","keys_url":"https://api.github.com/repos/keep-network/paillier/keys{/key_id}","collaborators_url":"https://api.github.com/repos/keep-network/paillier/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/keep-network/paillier/teams","hooks_url":"https://api.github.com/repos/keep-network/paillier/hooks","issue_events_url":"https://api.github.com/repos/keep-network/paillier/issues/events{/number}","events_url":"https://api.github.com/repos/keep-network/paillier/events","assignees_url":"https://api.github.com/repos/keep-network/paillier/assignees{/user}","branches_url":"https://api.github.com/repos/keep-network/paillier/branches{/branch}","tags_url":"https://api.github.com/repos/keep-network/paillier/tags","blobs_url":"https://api.github.com/repos/keep-network/paillier/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/keep-network/paillier/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/keep-network/paillier/git/refs{/sha}","trees_url":"https://api.github.com/repos/keep-network/paillier/git/trees{/sha}","statuses_url":"https://api.github.com/repos/keep-network/paillier/statuses/{sha}","languages_url":"https://api.github.com/repos/keep-network/paillier/languages","stargazers_url":"https://api.github.com/repos/keep-network/paillier/stargazers","contributors_url":"https://api.github.com/repos/keep-network/paillier/contributors","subscribers_url":"https://api.github.com/repos/keep-network/paillier/subscribers","subscription_url":"https://api.github.com/repos/keep-network/paillier/subscription","commits_url":"https://api.github.com/repos/keep-network/paillier/commits{/sha}","git_commits_url":"https://api.github.com/repos/keep-network/paillier/git/commits{/sha}","comments_url":"https://api.github.com/repos/keep-network/paillier/comments{/number}","issue_comment_url":"https://api.github.com/repos/keep-network/paillier/issues/comments{/number}","contents_url":"https://api.github.com/repos/keep-network/paillier/contents/{+path}","compare_url":"https://api.github.com/repos/keep-network/paillier/compare/{base}...{head}","merges_url":"https://api.github.com/repos/keep-network/paillier/merges","archive_url":"https://api.github.com/repos/keep-network/paillier/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/keep-network/paillier/downloads","issues_url":"https://api.github.com/repos/keep-network/paillier/issues{/number}","pulls_url":"https://api.github.com/repos/keep-network/paillier/pulls{/number}","milestones_url":"https://api.github.com/repos/keep-network/paillier/milestones{/number}","notifications_url":"https://api.github.com/repos/keep-network/paillier/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/keep-network/paillier/labels{/name}","releases_url":"https://api.github.com/repos/keep-network/paillier/releases{/id}","deployments_url":"https://api.github.com/repos/keep-network/paillier/deployments","created_at":"2018-04-02T00:45:16Z","updated_at":"2018-07-17T13:27:37Z","pushed_at":"2018-07-26T13:42:31Z","git_url":"git://github.com/keep-network/paillier.git","ssh_url":"git@github.com:keep-network/paillier.git","clone_url":"https://github.com/keep-network/paillier.git","svn_url":"https://github.com/keep-network/paillier","homepage":null,"size":128,"stargazers_count":0,"watchers_count":0,"language":"Go","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":1,"license":{"key":"mit","name":"MIT License","spdx_id":"MIT","url":"https://api.github.com/licenses/mit","node_id":"MDc6TGljZW5zZTEz"},"forks":0,"open_issues":1,"watchers":0,"default_branch":"master"}},"base":{"label":"keep-network:master","ref":"master","sha":"3eb21f405c6012a319b14ab5b4f6c3d982596ba5","user":{"login":"keep-network","id":30537626,"node_id":"MDEyOk9yZ2FuaXphdGlvbjMwNTM3NjI2","avatar_url":"https://avatars1.githubusercontent.com/u/30537626?v=4","gravatar_id":"","url":"https://api.github.com/users/keep-network","html_url":"https://github.com/keep-network","followers_url":"https://api.github.com/users/keep-network/followers","following_url":"https://api.github.com/users/keep-network/following{/other_user}","gists_url":"https://api.github.com/users/keep-network/gists{/gist_id}","starred_url":"https://api.github.com/users/keep-network/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/keep-network/subscriptions","organizations_url":"https://api.github.com/users/keep-network/orgs","repos_url":"https://api.github.com/users/keep-network/repos","events_url":"https://api.github.com/users/keep-network/events{/privacy}","received_events_url":"https://api.github.com/users/keep-network/received_events","type":"Organization","site_admin":false},"repo":{"id":127683627,"node_id":"MDEwOlJlcG9zaXRvcnkxMjc2ODM2Mjc=","name":"paillier","full_name":"keep-network/paillier","owner":{"login":"keep-network","id":30537626,"node_id":"MDEyOk9yZ2FuaXphdGlvbjMwNTM3NjI2","avatar_url":"https://avatars1.githubusercontent.com/u/30537626?v=4","gravatar_id":"","url":"https://api.github.com/users/keep-network","html_url":"https://github.com/keep-network","followers_url":"https://api.github.com/users/keep-network/followers","following_url":"https://api.github.com/users/keep-network/following{/other_user}","gists_url":"https://api.github.com/users/keep-network/gists{/gist_id}","starred_url":"https://api.github.com/users/keep-network/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/keep-network/subscriptions","organizations_url":"https://api.github.com/users/keep-network/orgs","repos_url":"https://api.github.com/users/keep-network/repos","events_url":"https://api.github.com/users/keep-network/events{/privacy}","received_events_url":"https://api.github.com/users/keep-network/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/keep-network/paillier","description":"Paillier cryptosystem implemented in Go","fork":true,"url":"https://api.github.com/repos/keep-network/paillier","forks_url":"https://api.github.com/repos/keep-network/paillier/forks","keys_url":"https://api.github.com/repos/keep-network/paillier/keys{/key_id}","collaborators_url":"https://api.github.com/repos/keep-network/paillier/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/keep-network/paillier/teams","hooks_url":"https://api.github.com/repos/keep-network/paillier/hooks","issue_events_url":"https://api.github.com/repos/keep-network/paillier/issues/events{/number}","events_url":"https://api.github.com/repos/keep-network/paillier/events","assignees_url":"https://api.github.com/repos/keep-network/paillier/assignees{/user}","branches_url":"https://api.github.com/repos/keep-network/paillier/branches{/branch}","tags_url":"https://api.github.com/repos/keep-network/paillier/tags","blobs_url":"https://api.github.com/repos/keep-network/paillier/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/keep-network/paillier/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/keep-network/paillier/git/refs{/sha}","trees_url":"https://api.github.com/repos/keep-network/paillier/git/trees{/sha}","statuses_url":"https://api.github.com/repos/keep-network/paillier/statuses/{sha}","languages_url":"https://api.github.com/repos/keep-network/paillier/languages","stargazers_url":"https://api.github.com/repos/keep-network/paillier/stargazers","contributors_url":"https://api.github.com/repos/keep-network/paillier/contributors","subscribers_url":"https://api.github.com/repos/keep-network/paillier/subscribers","subscription_url":"https://api.github.com/repos/keep-network/paillier/subscription","commits_url":"https://api.github.com/repos/keep-network/paillier/commits{/sha}","git_commits_url":"https://api.github.com/repos/keep-network/paillier/git/commits{/sha}","comments_url":"https://api.github.com/repos/keep-network/paillier/comments{/number}","issue_comment_url":"https://api.github.com/repos/keep-network/paillier/issues/comments{/number}","contents_url":"https://api.github.com/repos/keep-network/paillier/contents/{+path}","compare_url":"https://api.github.com/repos/keep-network/paillier/compare/{base}...{head}","merges_url":"https://api.github.com/repos/keep-network/paillier/merges","archive_url":"https://api.github.com/repos/keep-network/paillier/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/keep-network/paillier/downloads","issues_url":"https://api.github.com/repos/keep-network/paillier/issues{/number}","pulls_url":"https://api.github.com/repos/keep-network/paillier/pulls{/number}","milestones_url":"https://api.github.com/repos/keep-network/paillier/milestones{/number}","notifications_url":"https://api.github.com/repos/keep-network/paillier/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/keep-network/paillier/labels{/name}","releases_url":"https://api.github.com/repos/keep-network/paillier/releases{/id}","deployments_url":"https://api.github.com/repos/keep-network/paillier/deployments","created_at":"2018-04-02T00:45:16Z","updated_at":"2018-07-17T13:27:37Z","pushed_at":"2018-07-26T13:42:31Z","git_url":"git://github.com/keep-network/paillier.git","ssh_url":"git@github.com:keep-network/paillier.git","clone_url":"https://github.com/keep-network/paillier.git","svn_url":"https://github.com/keep-network/paillier","homepage":null,"size":128,"stargazers_count":0,"watchers_count":0,"language":"Go","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":1,"license":{"key":"mit","name":"MIT License","spdx_id":"MIT","url":"https://api.github.com/licenses/mit","node_id":"MDc6TGljZW5zZTEz"},"forks":0,"open_issues":1,"watchers":0,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/keep-network/paillier/pulls/8"},"html":{"href":"https://github.com/keep-network/paillier/pull/8"},"issue":{"href":"https://api.github.com/repos/keep-network/paillier/issues/8"},"comments":{"href":"https://api.github.com/repos/keep-network/paillier/issues/8/comments"},"review_comments":{"href":"https://api.github.com/repos/keep-network/paillier/pulls/8/comments"},"review_comment":{"href":"https://api.github.com/repos/keep-network/paillier/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/keep-network/paillier/pulls/8/commits"},"statuses":{"href":"https://api.github.com/repos/keep-network/paillier/statuses/7ab24f06419078cd13d4886aae5628f0f3f15d0d"}},"author_association":"NONE"}}
{"actor":{"display_login":"nkuba"}}