[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r24326 - in gnunet-java: . doc src/org/gnunet/construct src
|
From: |
gnunet |
|
Subject: |
[GNUnet-SVN] r24326 - in gnunet-java: . doc src/org/gnunet/construct src/org/gnunet/construct/parsers src/org/gnunet/dht src/org/gnunet/testing src/org/gnunet/util src/org/gnunet/voting test/org/gnunet/util |
|
Date: |
Mon, 15 Oct 2012 21:33:29 +0200 |
Author: dold
Date: 2012-10-15 21:33:29 +0200 (Mon, 15 Oct 2012)
New Revision: 24326
Modified:
gnunet-java/ISSUES
gnunet-java/doc/voting.bib
gnunet-java/doc/voting.pdf
gnunet-java/doc/voting.tex
gnunet-java/src/org/gnunet/construct/MessageLoader.java
gnunet-java/src/org/gnunet/construct/parsers/NestedParser.java
gnunet-java/src/org/gnunet/dht/DistributedHashTable.java
gnunet-java/src/org/gnunet/testing/TestingSubsystem.java
gnunet-java/src/org/gnunet/util/Client.java
gnunet-java/src/org/gnunet/util/HashCode.java
gnunet-java/src/org/gnunet/util/Server.java
gnunet-java/src/org/gnunet/voting/VotingSimulation.java
gnunet-java/test/org/gnunet/util/Assertion.java
Log:
fixed bugs from coverty, updated/corrected voting documentation
Modified: gnunet-java/ISSUES
===================================================================
--- gnunet-java/ISSUES 2012-10-15 17:22:37 UTC (rev 24325)
+++ gnunet-java/ISSUES 2012-10-15 19:33:29 UTC (rev 24326)
@@ -35,4 +35,14 @@
* when has an election ended? a point in time?
-one realistic use case of electronic voting would be the german e-petition
https://epetitionen.bundestag.de/
\ No newline at end of file
+one realistic use case of electronic voting would be the german e-petition
https://epetitionen.bundestag.de/
+
+
+
+
+-----------------------------------------------------
+
+
+* why is the commitment to the *public* key even necessary?
+
+* style question: punctuation and displayed equations
Modified: gnunet-java/doc/voting.bib
===================================================================
--- gnunet-java/doc/voting.bib 2012-10-15 17:22:37 UTC (rev 24325)
+++ gnunet-java/doc/voting.bib 2012-10-15 19:33:29 UTC (rev 24326)
@@ -45,3 +45,44 @@
publisher = {Springer-Verlag},
address = {London, UK, UK},
}
+
+
address@hidden {ddh,
+ author = {Boneh, Dan},
+ affiliation = {Stanford University Computer Science Department 94305-9045
Stanford CA 94305-9045 Stanford CA},
+ title = {The Decision Diffie-Hellman problem},
+ booktitle = {Algorithmic Number Theory},
+ series = {Lecture Notes in Computer Science},
+ editor = {Buhler, Joe},
+ publisher = {Springer Berlin / Heidelberg},
+ isbn = {978-3-540-64657-0},
+ keyword = {Computer Science},
+ pages = {48-63},
+ volume = {1423},
+ url = {http://dx.doi.org/10.1007/BFb0054851},
+ note = {10.1007/BFb0054851},
+ year = {1998}
+}
+
+
address@hidden,
+ author = {Menezes, Alfred J. and Vanstone, Scott A. and Oorschot, Paul C.
Van},
+ title = {Handbook of Applied Cryptography},
+ year = {1996},
+ isbn = {0849385237},
+ edition = {1st},
+ publisher = {CRC Press, Inc.},
+ address = {Boca Raton, FL, USA},
+}
+
+
address@hidden,
+ author = {Judson, T. W.},
+ citeulike-article-id = {3080999},
+ keywords = {bibliografia, review},
+ posted-at = {2008-08-04 14:16:24},
+ priority = {2},
+ publisher = {PWS Pub. Co.},
+ title = {{Abstract Algebra: Theory and Applications}},
+ year = {1994}
+}
Modified: gnunet-java/doc/voting.pdf
===================================================================
(Binary files differ)
Modified: gnunet-java/doc/voting.tex
===================================================================
--- gnunet-java/doc/voting.tex 2012-10-15 17:22:37 UTC (rev 24325)
+++ gnunet-java/doc/voting.tex 2012-10-15 19:33:29 UTC (rev 24326)
@@ -5,63 +5,84 @@
\begin{document}
+\newcommand{\todo}[1]{\marginpar{\footnotesize\emph{#1}}}
+
+\newcommand{\ZZ}{\mathbb{Z}}
+
\section{Parameters of the Encryption Scheme}
\begin{itemize}
- \item $p$ and $q$ are large primes, where $p=2q+1$ ($p$ is a so-called
Sophie Germain prime).
- \item $\alpha$ is a generator of $Z_{p}^{*}$.
- \item $G_q$ is the unique subgroup of $Z_{p}^{*}$ of order $q$. The discrete
logarithm is especially hard to solve for $G_q$.
- \item $g$ is a generator of $G_q$. Note that this is different from the
standard ElGamal scheme, where $g$ would be a generator of $Z_p^*$.
- \item $a \in Z_{p}^{*} \Leftrightarrow a^g \equiv 1 \mod{p}$
- \item Generally, all computations involving powers of $g$ are modulo $p$,
while
- polynomials / polynomial interpolation is done over modulo $q$.
+ \item There are $n$ authorities, $A_1 \dots A_n$.
+ \item Let $k$ be the minimum number of authorities required to jointly
decrypt a cyphertext.
+ \item \todo {How do we show that's feasable? Prime number theorem?}
+ Let $p$ and $q$ be large primes, where $p=2q+1$ ($q$ is commonly called a
Sophie Germain prime, $p$ a safe prime). A pair of such numbers can be found by
generating a random prime $q$ and checking if $2q+1$ is also prime.
+ \item \todo{Write down proof? Usually just stated as a fact in literature}
+ Let $g$ be a generator of $G_q$, where $G_q$ is the unique subgroup of
$\ZZ_p^*$ of order $q$. The \emph{Decisional Diffie--Hellman assumption} is
believed to hold for $G_q$, as $G_q$ is the subgroup of quadratic residues in
$\ZZ_q^*$. \cite{ddh}
+ \item The generator $g$ can be computed as follows \cite[Section 4.6]{hac}:
+ \begin{enumerate}
+ \item Repeatedly choose an $\alpha \in \ZZ_p^*$ at random, until it
satisfies $\alpha^q \ne 1$ and $\alpha^2 \ne 1$,
+ that is, the order of $\alpha$ is neither $q$, $2$ nor $1$. Then
$\alpha$ is a generator of $\ZZ_p^*$.
+
+ \emph{Proof:} By Lagrange's Theorem, $\ZZ_p^*$ has exactly two proper
non-trivial subgroups of order $p$ and $2$, respectively.
+ As $\alpha$ is neither of order $p$, $2$ nor $1$, it can only be a
generator of $\ZZ_p^*$.
+ \item Compute $g=\alpha^k$, where $k=(p-1)/q$. Then $g$ is a generator
of $G_q$.
+
+ \emph{Proof:} Let $ord(\cdot)$ be the order a group element. As $k$
divides $ord(\alpha)$, it follows from a standard result of group theory
\cite[Proposition 4.5]{algebra} that $ord(\alpha^k) = ord(\alpha)/k = q$.
+ \end{enumerate}
\end{itemize}
\section{Key Distribution}
\begin{itemize}
- \item There are $n$ authorities, $P_1 \dots P_n$
- \item $x = \sum_{i=1}^{n} x_i$ is the private key, every authority $P_i$
generates $x_i \in_R Z_q$.
- Note that we do not select $x_i$ from $Z_p$, as $p > q$ and
- $(\forall n \ge q) [ g^n = 1 ]$, by definition of $g$ as a generator of
$G_q$.
- \item Every authority $P_i$ publishes $h_i = g^{x_i}$.
- \item $h = g^{x}$ is the public key, and can be computed as $\prod_{i=1}^{n}
h_i$
- \item Let $k$ be the minimum number of authorities who can jointly restore
the private key.
- \item Every authority $P_i$ generates a random polynomial $f_i(z) =
\sum_{l=0}^{k-1} f_{il}^{l}$,
- where $f_{il} \in_R Z_q$ for $l \neq 0$ and $f_{i0}=x_0$. Note that
$f_i(0) = x_i$.
-
- \emph{Important}: The polynomials are evaluated over $Z_q$.
- \item Every authority $P_i$ publishes $(F_{ij})_{j=1,\dots,k-1}$, where
$F_{ij} = g^{f_{ij}}$.
- \item Now every authority $P_i$ secretly sends $s_{ij} = f_i(j)$ to each
authority $P_j$.
- \item $P_i$ verifies the shares received from $P_j$ is consistent with the
previously published values by
+ \item Let $x := \sum_{i=1}^{n} x_i$ be the private key. Note that no single
authority should be able to know $x$.
+ \item Every authority $A_i$ chooses a random $x_i \in \ZZ_q$, and publishes
$h_i := g^{x_i}$.
+ \item Let $h := g^{x}$ is the public key, which can be computed as $h =
\prod_{i=1}^{n} h_i$.
+ \item Every authority $P_i$ generates the random polynomial
+ \begin{equation}
+ f_i(z) = \sum_{l=0}^{k-1} f_{i,l}^{l},
+ \end{equation}
+ with $f_i(z) \in \ZZ_q[z]$, where $f_{i,0} = 0$ and $f_{i,l} \in \ZZ_q$ is
chosen randomly for $l \ne 0$.
+ It follows by definition that $f_i(0) = x_i$.
+ \item Every authority $P_i$ publishes $(F_{i,l})_{l=1,\dots,k-1}$, where
+ \begin{equation}
+ F_{i,l} = g^{f_{i,l}}
+ \end{equation}
+ is the commitment of authority $A_j$ to the value of $f_{i,l}$.
+ \item Now every authority $P_i$ secretly sends
+ \begin{equation} \label{eq:sendshares}
+ s_{i,j} = f_i(j)
+ \end{equation}
+ to each authority $P_j$.
+ \item \todo{Do we need to prove the consistency? Doesn't it just follow from
the fact that it is the same computation, only in the exponent of $g$?}
+ $P_i$ verifies the share received from $P_j$ is consistent with the
previously published values by
verifying that
- \[
- g^{s_{ij}} = \prod_{l=0}^{k-1} F_{jl}^{(i^l)}.
- \]
+ \begin{equation}
+ g^{s_{i,j}} = \prod_{l=0}^{k-1} F_{jl}^{(i^l)}.
+ \end{equation}
This equation follows directly from raising $g$ to both
- sides of $s_{ij} = \sum_{l=0}^{k-1} f_{il}^{l}$.
- \item $P_i$ computes his share of $x$ as $s_i = \sum_{j=1}^n s_{ji}$. This
works because evaluating $f(z) = \sum_{i=1}^{n} f_i(x)$ at $z=0$ gives $f(0) =
x$, and as $s_{ij}$ is interpolated by $f_i(z)$, the sum of all received shares
$s_j$ is interpolated by $f(z)$.
+ sides of equation \eqref{eq:sendshares}.
+ \todo{I think it should be illustrated why this works / what happens with
the polynomials}
+ \item $P_i$ computes his share of $x$ as $s_i = \sum_{j=1}^n s_{ji}$.
+ \item Each authority $A_i$ publishes
+ \begin{equation}
+ \sigma_i := g^{s_i}
+ \end{equation}
+ as a commitment to the received share.
\end{itemize}
-\section{ElGamal}
-To encrypt a cyphertext $m \in G_q$, the sender chooses a random $y \in_R Z_q$
and sends the pair $(c_1, c_2) = (g^y, m h^y)$.
-The decrypt the cyphertext, the receiver recovers the plaintext as $c_2 /
c_1^x = (m h^y) / g^{yx} = (m h^y) / h^y = m$.
-
-
\section{Cooperative Decryption}
\begin{itemize}
- \item The full private key can be restored by a set at least $k$ cooperating
authorities $\Lambda \subseteq \{P_1,\dots,P_n\}$, where $k \ge |\Lambda|$ the
decryption theshold set during the key distribution phase.
- \item This could be done using Lagrange interpolation, where the Lagrange
coefficients are
- \[
- \lambda_{j,\Lambda} = \prod_{\substack{
- P_l \in \Lambda \\ l \neq j} } \frac{l}{l-k}
- \]
- \item While the full private key $x$ should never be learned by a single
authority, it could be restored as
+ \item The full private key can be restored by a set at least $k$ cooperating
authorities $\Lambda \subseteq \{P_1,\dots,P_n\}$, $k \le |\Lambda|$, for
example by using Lagrange interpolation:
\begin{equation} \label{eq:pkey}
x = \sum_{P_j \in \Lambda} s_j \lambda_{j,\Lambda}
\end{equation}
- \item Let $\sigma_i$ denote $g^{s_i}$.
- \item To decrypt a cyphertext $(c_1, c_2) = (g^y, h^y m)$ each authority
$P_j$ broadcasts $w_j = c_1^{s_j}$.
+ where the Lagrange coefficients are
+ \begin{equation}
+ \lambda_{j,\Lambda} := \prod_{\substack{
+ P_l \in \Lambda \\ l \neq j} } \frac{l}{l-k}.
+ \end{equation}
+ Note that this formula is only used for the derivation of the cooperative
encryption process, and authorities never actually should cooperate to restore
the public key $x$.
+ \item To decrypt an ElGamal encryption $(c_1, c_2) = (g^y, h^y m)$ of the
message $m \in G_q$, each authority $P_j$ broadcasts $w_j = c_1^{s_j}$.
\item To prove that an authority has computed $w_j$ correctly, it has to
prove in zero-knowledge that
\[
s_j = \log_g \sigma_j = \log_{c_1} w_j,
@@ -93,7 +114,6 @@
\end{itemize}
This proof utilizes the fact that it is hard to compute $g^{ab}$ from $g$ and
$a$ without having $b$.
-
\section{Casting a vote}
\begin{itemize}
\item A vote has the form $(g^y, h^yG^b)$, where $G$ is a generator of $G_q$
(one could just use $G=q$), $b \in \{-1,1\}$ denotes the value of the vote, and
$y \in_R Z_q$.
@@ -157,10 +177,15 @@
\end{table}
+\appendix
+\section{ElGamal}
+To encrypt a cyphertext $m \in G_q$, the sender chooses a random $y \in_R Z_q$
and sends the pair $(c_1, c_2) = (g^y, m h^y)$.
+The decrypt the cyphertext, the receiver recovers the plaintext as $c_2 /
c_1^x = (m h^y) / g^{yx} = (m h^y) / h^y = m$.
+
\clearpage
\bibliographystyle{alpha}
-\bibliography{voting} % expects file "voting.bib"
+\bibliography{voting}
\end{document}
Modified: gnunet-java/src/org/gnunet/construct/MessageLoader.java
===================================================================
--- gnunet-java/src/org/gnunet/construct/MessageLoader.java 2012-10-15
17:22:37 UTC (rev 24325)
+++ gnunet-java/src/org/gnunet/construct/MessageLoader.java 2012-10-15
19:33:29 UTC (rev 24326)
@@ -23,6 +23,7 @@
package org.gnunet.construct;
+import com.google.common.base.Charsets;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
@@ -96,7 +97,7 @@
}
BufferedReader in = null;
try {
- in = new BufferedReader(new InputStreamReader(loc.openStream()));
+ in = new BufferedReader(new InputStreamReader(loc.openStream(),
Charsets.UTF_8));
String line;
while ((line = in.readLine()) != null) {
// skip empty lines and comments
Modified: gnunet-java/src/org/gnunet/construct/parsers/NestedParser.java
===================================================================
--- gnunet-java/src/org/gnunet/construct/parsers/NestedParser.java
2012-10-15 17:22:37 UTC (rev 24325)
+++ gnunet-java/src/org/gnunet/construct/parsers/NestedParser.java
2012-10-15 19:33:29 UTC (rev 24326)
@@ -60,6 +60,10 @@
if (optional) {
+ if (frameSizePath == null) {
+ throw new AssertionError("optional nested message needs
@FrameSize");
+ }
+
int remaining = frameOffset + ReflectUtil.justGetInt(frameObj,
frameSizePath) - srcBuf.position();
if (remaining < 0) {
throw new ProtocolViolationException("remaining size
negative");
Modified: gnunet-java/src/org/gnunet/dht/DistributedHashTable.java
===================================================================
--- gnunet-java/src/org/gnunet/dht/DistributedHashTable.java 2012-10-15
17:22:37 UTC (rev 24325)
+++ gnunet-java/src/org/gnunet/dht/DistributedHashTable.java 2012-10-15
19:33:29 UTC (rev 24326)
@@ -20,6 +20,7 @@
package org.gnunet.dht;
+import com.google.common.base.Charsets;
import org.gnunet.requests.Request;
import org.gnunet.requests.RequestQueue;
import org.gnunet.util.*;
@@ -364,6 +365,9 @@
description = "key used for the operation")
String key = null;
+
+ // todo: implement the following options
+ /*
@Argument(action = ArgumentAction.STORE_STRING,
shortname = "t",
longname = "type",
@@ -375,6 +379,7 @@
longname = "expire",
description = "expiration (ony use with --put)")
String expiration = null;
+ */
@Argument(action = ArgumentAction.STORE_NUMBER,
@@ -453,7 +458,7 @@
public void handleResult(AbsoluteTime expiration,
HashCode key, List<PeerIdentity>
getPath, List<PeerIdentity> putPath, BlockType
type, byte[] data) {
System.out.println("got result:");
- System.out.println(new String(data));
+ System.out.println(new String(data,
Charsets.UTF_8));
}
});
}
Modified: gnunet-java/src/org/gnunet/testing/TestingSubsystem.java
===================================================================
--- gnunet-java/src/org/gnunet/testing/TestingSubsystem.java 2012-10-15
17:22:37 UTC (rev 24325)
+++ gnunet-java/src/org/gnunet/testing/TestingSubsystem.java 2012-10-15
19:33:29 UTC (rev 24326)
@@ -20,6 +20,7 @@
package org.gnunet.testing;
+import com.google.common.base.Charsets;
import org.gnunet.util.Configuration;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
@@ -56,9 +57,8 @@
}
reader = new BufferedReader(new InputStreamReader(p.getInputStream()));
- writer = new OutputStreamWriter(p.getOutputStream());
+ writer = new OutputStreamWriter(p.getOutputStream(), Charsets.UTF_8);
-
String started;
try {
started = reader.readLine();
@@ -66,7 +66,7 @@
throw new TestingSetup.SetupException(e);
}
- if (!started.equals("ok")) {
+ if (started == null || !started.equals("ok")) {
throw new TestingSetup.SetupException("could not start service ('"
+ started + "')");
}
@@ -106,7 +106,7 @@
} catch (IOException e) {
throw new TestingSetup.SetupException(e);
}
- if (!line.equals("bye")) {
+ if (line == null || !line.equals("bye")) {
throw new TestingSetup.SetupException("service not destroyed
correctly");
}
System.out.println("read bye");
Modified: gnunet-java/src/org/gnunet/util/Client.java
===================================================================
--- gnunet-java/src/org/gnunet/util/Client.java 2012-10-15 17:22:37 UTC (rev
24325)
+++ gnunet-java/src/org/gnunet/util/Client.java 2012-10-15 19:33:29 UTC (rev
24326)
@@ -85,11 +85,18 @@
if (cfg == null) {
throw new AssertionError("Configuration may not be null");
}
+ if (!cfg.haveValue(serviceName, "PORT")) {
+ throw new Configuration.ConfigurationException(String.format("PORT
of service '%s' not specified", serviceName));
+ }
+ if (!cfg.haveValue(serviceName, "HOSTNAME")) {
+ throw new
Configuration.ConfigurationException(String.format("HOSTNAME of service '%s'
not specified", serviceName));
+ }
+
// get port of this service from the configuration
port = (int) cfg.getValueNumer(serviceName, "PORT");
// get the hostname from the configuration
hostname = cfg.getValueString(serviceName, "HOSTNAME");
- if (hostname.isEmpty()) {
+ if (hostname == null || hostname.isEmpty()) {
throw new
Configuration.ConfigurationException(String.format("hostname of service '%s'
empty", serviceName));
}
reconnect();
Modified: gnunet-java/src/org/gnunet/util/HashCode.java
===================================================================
--- gnunet-java/src/org/gnunet/util/HashCode.java 2012-10-15 17:22:37 UTC
(rev 24325)
+++ gnunet-java/src/org/gnunet/util/HashCode.java 2012-10-15 19:33:29 UTC
(rev 24326)
@@ -21,6 +21,7 @@
package org.gnunet.util;
+import com.google.common.base.Charsets;
import org.gnunet.construct.FixedSizeIntegerArray;
import org.gnunet.construct.Message;
@@ -50,7 +51,8 @@
}
/**
- * Create a HashCode of the String using SHA-512
+ * Create the HashCode of an UTF-8 String using SHA-512.
+ *
* @param s the string to hash
*/
public HashCode(String s) {
@@ -60,7 +62,7 @@
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException("crypto algorithm required but not
provided");
}
- byte[] data = digest.digest(s.getBytes());
+ byte[] data = digest.digest(s.getBytes(Charsets.UTF_8));
if (data.length != 64) {
throw new RuntimeException("error in SHA512 algorithm");
}
Modified: gnunet-java/src/org/gnunet/util/Server.java
===================================================================
--- gnunet-java/src/org/gnunet/util/Server.java 2012-10-15 17:22:37 UTC (rev
24325)
+++ gnunet-java/src/org/gnunet/util/Server.java 2012-10-15 19:33:29 UTC (rev
24326)
@@ -214,10 +214,14 @@
* @param stayConnected false if connection to the client should be
closed
*/
public void receiveDone(boolean stayConnected) {
+ if (currentReceive != null) {
+ throw new AssertionError("receiveDone() called, but still
waiting for message");
+ }
if (stayConnected) {
currentReceive = connection.receive(RelativeTime.FOREVER, new
MessageReceiver() {
@Override
public void process(GnunetMessage.Body msg) {
+ currentReceive = null;
if ((msg instanceof UnknownMessageBody) ||
!expectedMessages.contains(msg.getClass())) {
if (requireFound) {
logger.info("disconnecting client sending
unknown message");
Modified: gnunet-java/src/org/gnunet/voting/VotingSimulation.java
===================================================================
--- gnunet-java/src/org/gnunet/voting/VotingSimulation.java 2012-10-15
17:22:37 UTC (rev 24325)
+++ gnunet-java/src/org/gnunet/voting/VotingSimulation.java 2012-10-15
19:33:29 UTC (rev 24326)
@@ -1,7 +1,6 @@
package org.gnunet.voting;
import com.google.common.collect.Lists;
-import sun.security.x509.DistributionPoint;
import java.math.BigInteger;
import java.util.ArrayList;
Modified: gnunet-java/test/org/gnunet/util/Assertion.java
===================================================================
--- gnunet-java/test/org/gnunet/util/Assertion.java 2012-10-15 17:22:37 UTC
(rev 24325)
+++ gnunet-java/test/org/gnunet/util/Assertion.java 2012-10-15 19:33:29 UTC
(rev 24326)
@@ -25,7 +25,6 @@
public boolean success;
public int asserted;
public String message;
- public String failMessage;
public Assertion(String message) {
this.message = message;
@@ -35,8 +34,4 @@
success = b;
asserted += 1;
}
- public void assertTrue(boolean b, String failMessage) {
- assertTrue(b);
- this.failMessage = failMessage;
- }
}
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r24326 - in gnunet-java: . doc src/org/gnunet/construct src/org/gnunet/construct/parsers src/org/gnunet/dht src/org/gnunet/testing src/org/gnunet/util src/org/gnunet/voting test/org/gnunet/util,
gnunet <=