Collision-free one-wayish function mapping 32 bit to 32 bit

It is wanted a permutation of the 32-bit integers that is sizably more difficult to compute in the reverse direction than it is in the forward direction. Obviously, the ratio can't be more than $2^{31}$, since that's the cost of reversing the function by brute force. Also it is useful that the thing is parametrized; otherwise, it could be tabulated, and even reduced to a rainbow table.

I propose a construction using the Discrete Logarithm Problem in $\Bbb Z_p^*$ and cycle walking.

Let $p$ be a prime with $q=(p-1)/2$ prime and $p\bmod8=7$ (which implies that $2^q\bmod p=1$, and $2$ is a generator of the subgroup of quadratic residues modulo $p$, of prime order $q$). The function $f_p$ defined for integer $x$ by
$$x\mapsto f_p(x)=\min\big((2^x\bmod p),\,p-(2^x\bmod p)\big)$$
is a permutation of the integers in $[1,q]$ which is easy to compute in the forward direction, but requires solving the DLP in $\Bbb Z_p^*$ to reverse. Illustration for $p=47$

   x =  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
fp(x)=  2  4  8 16 15 17 13 21  5 10 20  7 14 19  9 18 11 22  3  6 12 23  1

This property also holds if we add two parameters $a$ and $b$ with $1\le a<q$ and $0\le b<q$, giving
$$x\mapsto f_{(p,a,b)}(x)=\min\Big(\big({(2^a)}^{x+b}\bmod p\big),\,p-\big({(2^a)}^{x+b}\bmod p\big)\Big)$$

With $p>2^{33}$, the function ${\tilde f}_{(p,a,b)}$ obtained by iterating that $f_{(p,a,b)}$ while the result is larger than $2^{32}$ is a permutation of the integers in $[1,2^{32}]$.

And now $x\mapsto h_{(p,a,b)}(x)={\tilde f}_{(p,a,b)}(x+1)-1$ defines a permutation $h_{(p,a,b)}$ of the 32-bit integers, as desired, which is considerably easier to evaluate in the forward direction than it is to invert.

As an illustration, for $p=\lceil2^{32}\pi\rceil+3062=13493040767$, $a=1$, $b=42$, it is easy to compute $h_{(p,a,b)}(4)=2511267353$ (because $f_{(p,a,b)}(5)=5073155518>2^{32}$, $f_{(p,a,b)}(5073155518)=5723706427>2^{32}$, $f_{(p,a,b)}(5723706427)=2511267354\le2^{32}$). But it is sizably more difficult to solve $h_{(p,a,b)}(x)=2919107273$ for $x$. Try it!

I guesstimate that inversion for one output is several hundreds times harder than direct computation even using sophisticated algorithms to solve the DLP (index calculus or NFS); thousands times harder with simpler algorithms (BSGS or Pollard's ρ); and hundreds thousands times harder by brute force.

In a white box context, it might be slightly better to have the implementation contain $2^a\bmod p=g$ rather than $a$, and implement ${(2^a)}^{x+b}\bmod p$ as $g^{x+b}\bmod p$ or $g^{(x+b)\bmod q}\bmod p$. On the other hand, in a black box context, the forward implementation can implement ${(2^a)}^{x+b}\bmod p$ as $2^{(a\,x+b)\bmod q}\bmod p$, which allows a slightly faster evaluation.

The number of iterations of $f_{(p,a,b)}$ is about $p/2^{33}$ on average, and for $p<2^{34}$ is more than $k$ with probability less than about $2^{-k}$. In order to slow down evaluation (and reversal), we can chain several $h_{(p,a,b)}$ using different $p$, which is better that an overlarge $p$ on two accounts: the evaluation time tends to depend less on $x$; and attacks making heavy pre-computations to later efficiently solve multiple discrete logarithm problem in the same $\Bbb Z_p^*$ are thwarted.

There seems to be better constructions (in the sense of making the ratio of reverse to forward cost higher) using the DLP on a super-singular elliptic curve; see this and its comments, and perhaps this for the curve.


Homomorphic encryption and approximated GCD

This cipher is broken against chosen plaintext attack. Submit encryptions of 0 to obtain a set where each element is composed of p times some random q. Then, compute the gcd of some of the pairs until you acquire p.

If p and q are not prime, you will require more then two pairs.

You may be interested in the DoubleMod construction.


It depends on what algorithm (determined by key type) and padding you use.

If the key is a DSA key, or an ECC key used for ECDSA, those algorithms normally use randomized signatures to remain secure, and OpenSSL does so. (There is a variant scheme that makes k unique and unpredictable without making it truly random, but it is not widely used and not implemented in OpenSSL.)

If the key is an RSA key, OpenSSL supports 3 RSA paddings other than none: pkcs1 (more exactly the type-1 scheme of PKCS#1 through v1.5, now retronymed RSASSA-PKCS1-v1_5), pss, and x931. dgst -sign for RSA defaults to pkcs, which is deterministic and should not produce varying results; if it does please edit your question with details (preferably using a test key). Only if you specify -sigopt rsa_padding_mode:pss should you get a randomized result.

Note RSA encryption is different, and OpenSSL supports two paddings other than none: pkcs1 (this time meaning RSAES-PKCS1-v1_5) and oaep, both of which are randomized; the newer OAEP is randomized in a way that is provably secure which the older v1_5 scheme does not.


Is it safe to seed a random number generator from system time?

Yes, it is unsafe to seed a PRNG with only with the system time.  No, that's not all Bouncy Castle's SecureRandom does.

The SecureRandom default constructor calls SetSeed(GetSeed(8)); which calls Master.GenerateSeed(length); which calls SetSeed(DateTime.Now.Ticks); which is misleading because SetSeed only adds seed material to an already existing prng (the static instance called Master).  If you look at the static declaration for private static SecureRandom Master you'll see that it actually seeds itself from a combination of Ticks and ThreadedSeedGenerator.

Why the system time is not enough

Using just the system time would be unsafe.  The whole point of a crypto random generator is to be unguessable by an adversary, and by using the system time as a seed to the random number generator, you make it easy for an adversary to guess your seed and hence your random output.

DateTime.Now.Ticks has precision of 10 million ticks per second.  Suppose an attacker knows what time you generated a key, +/- 1 second.  They only need to make 20 million guesses ($2^{20}$ or so) in order to guess your random seed.  This is likely crackable in a matter of seconds with a modern laptop.

Suppose an attacker has absolutely no idea what time you generated some key.  They only know it was after – let's say – the year 2000.  Since it's 2014 now, the entire space of 14 years occupies 51-52 bits.  log2(10000000*60*60*24*365*14) ~= 51.97…  This means the absolute highest level of entropy that you're likely to have in anything generated from system time is around 51 bits, which is small enough to be easily crackable, and realistically, you'll never even come close to that.


mpz_nextprime states in the documentation and source (file: mpz/nextprime.c) that it simply finds the next prime larger than the provided input. There are various methods of doing so (depending on how efficient it tries to be), but they should all produce the same answer. Looking at the code, mpz_nextprime first tests a number against a large quantity of small primes to see if they are a factor. If not, mpz_nextprime uses a probabilistic Miller-Rabin test. If the number passes the MR test, it is output as prime; if it doesn't, it is incremented by 2 and tested again. (Like OpenSSL, as mikeazo linked to.)

mpz_nextprime used to use Miller-Rabin with 10 tests, a testing strength that could be argued to be weaker than desired. But looking at the source for the current version (5.0.4) they've changed to use 25 tests, which is sufficiently safe.

Now, regarding the method: A potential problem with generating a random number and then "walking" to the next largest prime is that primes are not evenly distributed, so neither are the gaps between them. If you have consecutive primes $p_i$ and $p_{i+1}$, any randomly generated number between $p_i$ and $p_{i+1}$ would get mapped to $p_{i+1}$. Primes that follow large gaps are more likely to be chosen, and primes that follow smaller gaps would be less likely to be chosen. You would be imposing a non-uniform distribution on your choice of primes. (Read a little more here.)

That isn't necessarily a problem, though, and I can't say I've ever seen serious concern raised over it. OpenSSL probably has sufficient confidence in their method. Although, of course, the "perfect" way to ensure your have a prime number distribution that is even is to just generate random numbers until one of them is prime. Although it is probably a little slower than "increment-and-test" on average, it can't be much slower. One advantage of the increment-and-test method that it is deterministic, since there is guaranteed to be a prime between $p$ and (approximatively) $p + \sqrt(p)$, but given the frequency of primes ($log(p)$), I would think that such weak work limit wouldn't be a concern.


What is the probability of finding 4 equal bytes?

There are $2^8$ one-byte (technically, one-octet) patterns. That implies there are $2^8$ four-octet strings where all four octets are identical out of $2^{32}$ possible patterns. $\frac{2^8}{2^{32}}=2^{-24}$


What is the time complexity of the basic components of a symmetric cipher?

I cannot find anything simple on time complexity for cryptographic components (functions?) as describable above

You wont really find anything because those components are generally not described that way. There are simply too many ways of implementing each component in hardware and software on multiple platforms, and they do not always obey the rules of big-O notation, a 1-bit XOR and a 64-bit XOR may take the exact same amount of time, but transform a 64X difference in data. Shifting by 1-bit usually takes the same amount of time as shifting by several bits. In hardware, a permutation may be done by arranging wires in a specific pattern, and take 0 additional time to complete, whereas in software a complex series of operations may be required to rearrange the data (like the DES initial permutation for example).

Things like matrix multiplication can be implemented as table lookups or as a series of more simple operations, sometimes bitsliced to improve performance. Increasing the size of the matrix can have wildly different outcomes in terms of time requirements based on the implementation method, since generating a table is only needed once.

Simply put, it is more common to describe the performance of those operations in cpu cycles on a specific platform, individually and as a group of operations, and as the entire algorithm. Then a given implementation/platform combination can be compared, and the best or most common used as a benchmark.


Is there a way or how to predict the output size as a result of encryption?

This depends on:

Precise choice of encryption algorithm
Choice of representation for the ciphertext
Size of additional metadata stored with each ciphertext

On #1, 3DES, AES128, AES192 are block ciphers, so they're not ready-to-use end-user variable message length encryption algorithms.  You use them in the context of some mode, which you should really think of the "real" encryption algorithm.  For example, one very common mode nowadays is GCM (Galois Counter Mode), which instantiated with AES we would call AES-GCM.  Some modes require ciphertexts to be a multiple of the block cipher block size as well, which means that plaintexts get padded to fill up a block.

So first and foremost, the size of a ciphertext depends on the mode.  AES-GCM ciphertexts, in binary, are generally 16 bytes longer than the plaintexts.  And you may need an additional 12 bytes to store the nonce.

Now, #2 ("choice of representation for the ciphertext"): ciphers operate on binary data and produce binary output.  But many systems and developers are very allergic to binary data and prefer all data to be in some sort of plain-text format (e.g., XML, JSON).  So the raw binary output of a cipher is in practice often encoded into ASCII using a binary-to-text encoding like Base64.  This adds about a 33% overhead over raw binary size.

Point #3 ("size of additional metadata stored with each ciphertext"): Often you want to store additional information with each ciphertext, for example metadata related to key management:

A key identifier that allows you to locate, for each ciphertext, the key that was used to encrypt it.
An encrypted data encryption key (DEK).  This is part of a common key management strategy where ciphertexts are encrypted with an ephemeral DEK key, which is then encrypted with a master key (a key encryption key or KEK), and the encrypted DEK is stored alongside the ciphertext.

So you need to work out a number of details to get a precise answer to your question.


How to steganographically embed data in cropped/resized images?

This is a big research field with a lot of different techniques. The right term here is "watermarking". Similar to steganography but with different requisites: we hide only a mark and we want to be resistant to cropping, resizing and others (blurring, compression, noise addition, ...). One approach to resist cropping is to copy the mark several times in different positions of the image. One approach to resizing is to hide information by modulating the DCT coefficients.


Why must an elliptic curve group for ECC have prime order?

Well, it doesn't have to. In short, as a consequence of the Pohlig-Hellman algorithm the ECDLP is only as hard as the largest prime order subgroup. So the requirement is that there exist a large prime order subgroup. In (a little) more detail:

Elliptic-curve cryptography is mostly based on the Elliptic Curve Discrete Logarithm Problem (ECDLP). That means that given some elliptic curve $E$, we want that the ECDLP is hard in $E$.

Suppose that the group $E$ has order $p_1p_2\cdots p_n$ for some (not necessarily distinct) primes $p_1,\ldots,p_n$. Then the Pohlig-Hellman algorithm reduces the ECDLP in $E$ to ECDLP in subgroups $G_i$ of order $p_i$ respectively. If all the $p_i$ are small, this means that ECDLP is easy in all $G_i$, e.g. by simply building a table of all $p_i$ elements. This leads to a solution of an ECDLP in $E$. Hence to make the ECDLP hard in $E$, we need that at least one of the $p_i$ is large.

For example, prime order elliptic curves trivially have a large prime order subgroup (the group itself!). On the other hand, Montgomery curves (e.g. Curve25519) have order 4*n, so can never be prime. To securely base protocols on Montgomery curves we have to make sure that $n$ has at least one very large prime factor.


Performing a dictionary attack on RSA/ECB with no padding

If the public modulus was generated properly, option 2 (brute force dictionary search of candidate plaintext) will be faster. Option 1 (factoring a ≈512-bit RSA integer) is feasible, but can be quite compute-intensive even with the best known algorithm (GNFS). On the other hand, if random padding was used (as it should, and would be in any good practice), option 2 would not be feasible.

First things are to determine how exactly a dictionary word would be encrypted, including formatting of the ciphertext.

I think Python 3 might be acceptably fast just checking if pow(m,e,n)==c where m varies over the plaintexts appropriately converted to integer as in the encrption, and c is the ciphertext appropriately converted back to integer. For (perhaps only slightly) better speed, write a compiled program using GMP.


ECDH - when are the domain parameters shared and how?

How the parameter set to use is established depends on the (application) protocol entirely. They need to be established before the key agreement operation takes place, but there aren't really any other requirements. Usually they are shared by name or OID (short for Object Identifier usually encoded using Abstract Syntax Notation One or ASN.1) in the protocol, but it is also possible to just allow a single curve for a specific (version of) a protocol. Quite often the domain parameters are simply listed and given an index number in a protocol as well, if just to save space.
Sometimes the entire set of parameter values are simply send over (which is what I would call "sharing"). This is for instance the case for some smart card based protocols as it is a bit unwieldy to store all the curves in the limited storage available. In general you want to trust the party that sends over the parameters though. If some curves or sizes are optional then you may need to come to some kind of agreement between the parties about which curve to use, although I haven't seen many flexible protocols like that. Sharing parameters isn't all that common, usually well known curves are used so there is no need to share the parameter sets.
When it comes to card verifiable certificates in ePassports, the root certificate defines which domain parameters are to be used. The underlying keys (it contains 3 levels) will always use the same curve as the root. And staying with ePassports, there is also a scheme called PACE where the new domain parameters are calculated from a previous set (the sets only differ w.r.t. base point G of course, not the entire set).


The RNG used (arguably misused) as a PRF for key derivation in EAP-AKA and also EAP-SIM was defined as a small almost incidental part of FIPS 186-2 (2000) plus change notice 1 (2001). The URL in the 2006 RFCs http://csrc.nist.gov/publications/fips/fips186-2/fips186-2-change1.pdf is no longer valid, because 186-2 has been superseded by 186-3 (2009) and 186-4 (2013) and those newer versions no longer define the RNGs for digital signatures; instead they refer to a separate publication, first SP800-90 and now SP800-90A, whose focus is random generators.

However, 186-2 is still available in the CSRC archive at https://csrc.nist.gov/publications/fips/archive/fips186-2/fips186-2-change1.pdf . The original definition of two RNGs, with two applications that both involve generating numbers less than a number called 'q' (the subgroup order for the Digital Signature Algorithm DSA), is in Appendix 3 starting on page 16 (PDF page 19):

  The algorithms employ a one-way function G(t,c), where t is 160 bits, c is b bits (160 ≤ b ≤ 512) and G(t,c) is 160 bits. One way to construct G is via [a modification of] the Secure Hash Algorithm (SHA-1), as defined in the Secure Hash Standard (SHS). The 160-bit message digest output of the SHA-1 algorithm when message M is input is denoted by SHA-1(M). A second method for constructing G is to use the Data Encryption Standard (DES). The construction of G by these techniques is discussed in sections 3.3 and 3.4 of this appendix.

  3.1. ALGORITHM FOR [generating x0..m-1]
  Step 1. Choose a new, secret value for the seed-key, XKEY.
  Step 2. In hexadecimal notation let
      t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0
    This is the initial value for H0 || H1 || H2 || H3 || H4 in the SHS.
  Step 3. For j = 0 to m - 1 do
    a. XSEEDj = optional user input.
    b. XVAL = (XKEY + XSEEDj) mod 2b.
    c. xj = G(t,XVAL) mod q.
    d. XKEY = (1 + XKEY + xj) mod 2b.

However, the change notice at PDF page 71 first alters section 3.1 to:

  Step 1. Choose a new, secret value for the seed-key, XKEY .
  Step 2. In hexadecimal notation let
      t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0.
    This is the initial value for H0 || H1 || H2 || H3 || H4 in the SHS [FIPS 180-1].
  Step 3. For j = 0 to m - 1 do
    3.1 XSEED j = optional user input
    3.2 For i = 0 to 1 do
      a. XVAL = (XKEY + XSEED j) mod 2b
      b. wi = G(t, XVAL ).
      c. XKEY = (1 + XKEY + wi) mod 2b .
    3.3 xj = (w0 || w1) mod q

and then adds that this algorithm can be used for 'General Purpose Random Number Generation' by removing the 'mod q' term from the computation of xj.

You can see this is now the algorithm you quote from Appendix A of rfc4187 (and Appendix B of rfc4186) except those set XSEEDj to zero (as stated in section 7 of each RFC) and change the notation because RFCs are ASCII-text (| for concatenation, ^ for superscript/exponentiation, and _ for subscript).

You want the G function based on SHA-1 specified in 3.3:

  G(t,c) may be constructed using steps (a) - (e) in section 7 of the Specifications for the Secure Hash Standard. Before executing these steps, {Hj} and M1 must be initialized as follows:

  i. Initialize the {Hj} by dividing the 160 bit value t into five 32-bit segments as follows:
              t = t0 || t1 || t2 || t3 || t4
        Then Hj = tj for j = 0 through 4.

  ii. There will be only one message block, M1, which is initialized as follows: M1 = c || 0512-b (The first b bits of M1 contain c, and the remaining (512-b) bits are set to zero). Then steps (a) through (e) of section 7 are executed, and G(t,c) is the 160 bit string represented by the five words:
      H0 || H1 || H2 || H3 || H4 at the end of step (e).

Now there's a snag. FIPS186-2, and rfc4187 and rfc4186, refer to an earlier version of the Secure Hash Standard, FIPS180-1 (1995), which has also been superseded, by 180-2 (2002,2004) 180-3 (2008) and 180-4 (2011, 2015), and as far as I can tell is NOT officially archived. But Google finds http://securityv.isu.edu/isl/fip180-1.html whose section 7 a-e are the per-block 'compression function' of SHA-1, matching the substance of 6.1.2 in newer standards though different in notation. The same logic is duplicated, perhaps a little more readably, in rfc3174 section 6.1.

The EAP RFCs specify the initial value of H (now called H(0)) is 't' which is the standard initial value for SHA-1 (section 6 in 180-1, 5.3.1 in newer versions), so this amounts to the same thing as SHA-1 for a single-block message EXCEPT WITH DIFFERENT PADDING than defined by 180.

And there's the rub. Implementations of SHA-1 you find in modern systems are almost always designed to do the standard padding, not the zero-padding you need. Unless you can get at the internals -- which will depend on exactly what implementation(s) or platform(s) you use (and that part probably does belong on Stackoverflow where the question was originally posted) -- you'll have to duplicate the code for SHA-1, with this (tiny) modification. Fortunately SHA-1 is used for so many things, and very many of them open source, this shouldn't be too hard; for one possibility, rfc4634 (which updates 3174) has C code under a license that (IMOIANAL) is equivalent to CC-BY.


Which block cipher mode(s) is most appropriate in these applications?

The first application is for decryption on a multicore processor. I assume any of ECB, CBC, CFB or CTR would be suitable since decryption would be faster when performed in parallel, but are any of them significantly more suitable than the others and how?

CTR, CBC and CFB all allow parallel decryption. CTR allows you to decrypt any ciphertext block independently, while the other two allow you to decrypt a block if you know the ciphertext of both it and the previous one.

However, of those only CTR also allows parallel encryption.
ECB is insecure in most cases, so it shouldn't be used, but also supports both.

  The second is where it is preferred/desired to use a processor's idle time for precomputing encryption or decryption tasks before the plaintext or ciphertext is available. Not really sure how to tackle this one.

Like ECB, both CBC and CFB require knowing the plaintext to compute any block encryptions (beyond the first block, in the case of CFB). CTR allows you to compute the entire keystream in advance.

However, in the real world you would most likely want to use authenticated encryption. Meaning you'd want to consider authenticated cipher modes as well. Many of them use CTR internally for the encryption part, fulfilling both of the above. GCM is the most common, and also allows the authentication part to be calculated in parallel.


Secure Computation: Reactive Functionalities in the Hybrid Model for Standalone Security

First, your question about that footnote. I guess I can expand on it since I'm probably the one who wrote the footnote.

You can model a reactive functionality as follows:

Fix an initial value for the (private, internal) state $s$
Repeat forever:

Receive input $x$ from Alice and $y$ from Bob
Compute $(s', a, b) \gets f(s, x,y)$
Give output $a$ to Alice and $b$ to Bob, and set $s := s'$

Here $f$ is a deterministic function that characterizes this functionality. The initial value of $s$ is public information. What is being proposed in that footnote is the following protocol for the reactive functionality:

Alice & Bob fix secret shares $s_A, s_B$ for the initial value of $s$
Repeat forever:

Perform a secure computation of the non-reactive functionality:

  $g\Big( (s_A, x), (s_B,y) \Big) = \Big( (a,s'_A), (b, s'_B) \Big)$, where $(s',a,b) \gets f\big(\textsf{Reconstruct}(s_A,s_B), x,y\big)$ and $(s'_A, s'_B) \gets \textsf{Share}(s')$

in other words, Alice gives input $(s_A,x)$ and Bob gives input $(s_B,y)$ to this computation. Alice receives output $(a, s'_A)$ and Bob receives $(b,s'_B)$.
Alice updates her share $s_A := s'_A$ and Bob does too: $s_B := s'_B$

This protocol's invariant is that at every step the parties hold secret shares of the reactive functionality's internal state. At each step they perform a non-reactive computation that reconstructs the internal state and performs one step of the reactive functionality.

For semi-honest security any standard secret-sharing scheme is fine to use here. For malicious security, you need to be able to detect tampering of shares (since nothing prevents Alice from receiving $s'_A$ as output in one round and giving something other than $s'_A$ as input to the next round).

Now for your specific concern about commitment. You are right that there is communication between the parties during the lifetime of the commitment functionality. And if you think of the entire lifetime of the commitment functionality as one unit, this is problematic for rewinding/simulation in the standalone setting.

But the commitment functionality has two phases: commit phase & reveal phase. The way around the issue is to require simulators that are local to each of these phases. That is, when you are simulating the reveal phase, you can't rewind to before the reveal phase (although you may have done some rewinding in the commit phase, you are now stuck with that history after you declare the commit phase to be done).

If you look at the typical security definitions for commitment, that is exactly what they say.

In a simulation-based definition for commitment, we define binding by means of an extraction game. A corrupt committer can't distinguish between committing to an honest receiver vs committing to a rewinding simulator which extracts the committed value. This is really just a statement about the commit phase only (well, mostly).
We define hiding by means of an equivocation game. A corrupt receiver can't distinguish between talking to an honest committer vs talking to a locally-rewinding simulator which doesn't get the value until the reveal phase starts. Again, this simulator is allowed to rewind in the commit phase, and in the reveal phase, but it is not allowed to rewind the reveal phase all the way back in time to the commit phase.

If you are wondering whether this means that we're already requiring stronger UC security rather than standalone, it's helpful to think of a commitment protocol that has a 10-round commit phase and 10-round reveal phase. If this protocol was UC-secure, you could use it in a larger protocol, and ask the parties to send additional messages in round 7 of the commit phase. But it's no good for the standalone definition I gave, since there may be rewinding taking us back and forth across round 7 many times. So this standalone definition says: each individual phase of the reactive functionality should be "atomic". That is indeed what happens in the description of your coin-tossing protocol: do the commit phase, wait for it to be done, only then send your random bit. So that is why your coin-tossing protocol is standalone-secure when instantiated with standalone-secure commitment.

In summary, communication between parties is kosher during the lifetime of the reactive functionality, but only as long as it is in between the distinct "phases" of the reactive functionality.


How hard are discrete logarithms problems in $\mathbb Z^{*}_{n}$ and $\mathbb Z^{*}_{n^2}$, where $n$ is the RSA $n=pq$

No, it is not possible to compute $\lambda$ easily.  Specifically, if you have a black box that, given a random instance $c$, $c^\lambda \bmod n^2$, was able to recover $\lambda$ with nontrivial probability, you can use that to factor $n$ with nontrivial probability.  Hence, if we believe the factorization problem is hard, we must also believe that this modified discrete log problem is hard.

One way to arrive at that is "if you can find $\lambda$ given a random instance, you can compute (a multiple of) the order of a random element, and if you can do that, you can factor".

To compute this order using the black box, you take your random element $r$, select a random exponent $k>1$ ($k$ needs to be relatively prime to $pq(p-1)(q-1)$, making it a large random prime works), and then query your DLOG oracle for discrete log $(r^k)^\lambda = r \bmod n^2$; once you know $\lambda$, you also know that $r^{k\lambda-1} = 1 \bmod n$ (because if $(r^k)^\lambda = r \bmod n^2$, then $(r^k)^\lambda = r \bmod n$ as well).  That is, the order of $r$ is a divisor of $k\lambda-1$.

Once you have that multiple of an order $x = k\lambda-1$, you can then factor $n=pq$ by considering the odd value $y = x/2^j$, and then for random values of $s$ ($r$ works well for an initial guess), consider the sequence $(s^y, s^{2y}, s^{4y}, ..., s^{x})$.  If we see a 1 in the sequence proceeded by a value $z$ other than 1 or $n-1$, then we can factor; the factors are $gcd(n, z-1)$ and $gcd(n, z+1)$.  And, if $r$ was chosen randomly, then with high probability this procedure will find a factorization after a modest number of random $s$ values.


Can quantum algorithms solve the approximate GCD hard problem efficiently?

In the $(\gamma, \eta, \rho)$-AGCD problem, all the samples are of the form
$$x_i := pq_i + r_i$$

for $q_i$ uniform from $[0, 2^\gamma / p [ ~ \cap \mathbb Z$;

$r_i$ uniform from $]-2^\rho, 2^\rho [ ~ \cap \mathbb Z$;

and $p$ a fixed random prime of $\eta$ bits.

This problem is believed to be quantum secure. See, for instance, this paper published in PKC 2017.

Moreover, a variant of the AGCD problem in which the noise term is sampled from a continuous Gaussian distribution, then it is rounded to integer (instead of being uniform in the integer interval from $-2^\rho$ to $2^\rho$) was proven to be basically equivalent to the LWE (see this paper published in EUROCRYPT 2015), and LWE is also believed to be quatum secure.

However, you have to be careful with other variants of the AGCD problem that are commonly used. For example, the "first is noiseless" variant (known by noise-free AGCD), in which $x_0 := pq_0$, that is, a multiple of $p$ without noise, is used in several papers and is obviously not quantum secure, as one can quantumly factor $x_0$.


Cardinality of the group of units in a cyclotomic ring?

The $n$th cyclotomic polynomial $\Phi_n\in\mathbb Z[x]$ is irreducible in $\mathbb F_q[x]$ if and only if $q$ is a generator of $(\mathbb Z/n)^\times$ (proof).
Hence, unfortunately, the polynomial $x^n+1$ is never irreducible modulo $q$ if $n>4$ is a power of two: The group $(\mathbb Z/n)^\times$ is not cyclic in that case. Thus it may indeed happen that the polynomial chosen in NTRU is not invertible.

Since I am not aware of any exact results, we shall derive a generic lower bound for the cardinality of $(\mathbb F_q[x]/(x^n+1))^\times$.
(By "generic", I mean that the following is not specific to cyclotomic polynomials. I suspect one can obtain much better bounds by using cyclotomic theory.)

I will assume $q\geq3$. Then the polynomial $x^n+1$ is square-free over $\mathbb F_q$ since $\gcd(x^n+1,nx^{n-1})=1$.
Decompose $x^n+1$ into (therefore distinct) irreducible factors $g_i\in\mathbb F_q[x]$ of degrees $e_i:=\deg g_i$.
By the Chinese remainder theorem, we have an isomorphism
$$
    \varphi\colon\quad
    \mathbb F_q[x]/(x^n+1)
    \;\cong\;
    \prod_{i=1}^r\underbrace{\mathbb F_q[x]/g_i}_{\cong\ \mathbb F_{q^{e_i}}}
    \text.
$$
Composing this isomorphism with projections to the direct factors $\mathbb F_q[x]/g_i$ yields ring homomorphisms
$$
    \pi_i\colon\quad
    \mathbb F_q[x]/(x^n+1) \;\to\; \mathbb F_{q^{e_i}}
$$
with the property that an element of $\mathbb F_q[x]/(x^n+1)$ is invertible if and only if its image under each $\pi_i$ is invertible, i.e., non-zero. Hence the probability that an element $f\in\mathbb F_q[x]/(x^n+1)$ chosen uniformly at random is a unit is
$$
    \Pr[\text{unit}] \;=\; \prod_{i=1}^r (1-1/q^{e_i})
    \text.
$$
How bad can this become? In the worst case, we have $r=n$ and all $e_i=1$, hence
$$
    \Pr[\text{unit}] \;\geq\; (1-1/q)^n
    \text.
$$

When considering small $q$ and large $n$, this bound becomes quite low quickly, but keep in mind that it is a worst-case estimate. In practice, it seems that the $e_i$ are typically much greater than $1$.

Moreover, in the NTRU scenario, $q$ is quite big: The parameters recommended, depending on the source, are roughly $q\approx 2000$ and $n\approx 1000$, yielding
$$
    \Pr[\text{unit}] \;\geq\; \frac12
    \text,
$$
so one can easily find a unit within a few tries with very large probability.


How modern messengers encryption keys can't be hacked

Aren't they delievering by the network the same as the encypted messages?

No. At least not in the plain.

  What doing it end-to-end encrypted?

Try to search for the key agreement protocol (e. g. Diffie-Hellman ) and asymmetric encryption (e.g. RSA ).

The "asymmetric" encryption allows sending encrypted and signed messages without sharing the private (secret) key.

Very simplistically explained - each actor creates a key pair (with a public and private part) and the actors will exchange their public key. That allows both actors to securely create a shared secret even on an unsecure channel


What is the difference between chosen-plaintext attack and adaptive-chosen-plaintext attack?

With chosen-plaintext attack, the attacker is allowed to choose an arbitary amount of plaintext to encrypt. After that he/she can't do that again, he/she has to work with the current data.

With the adaptive-chosen-plaintext attack, he/she can do the same as with the chosen-plaintext attack, but is also allowed to encrypt new data after the attacker has looked and analyzed previous encrypted bits. He/she can, based on the already encrypted data, choose new data to further advance his/her attack.


Without explaining all details of ECDSA, a public key consists of a curve $E(\mathbb{F}_p)$ and a point $P \in E(\mathbb{F}_p) \setminus \{0\}$.

The point $P$ is a random point chosen from all points of the curve (minus the point at infinity). Because the number of points must be large to be secure, it is very unliky that two randomly generated public keys share the same point.

For example, for secp256k1 (the curve used for bitcoin) you have $115792089237316195423570985008687907852
837564279074904382605163141518161494337 - 1$ possible points.

Without more details of the applications, it is probably safe to use the coordinates of the point to identify peers.


Doubling the block length of a given block cipher

Parallel construction

Then my first feeling is that you wouldn't lose that much in security however there are several drawbacks.

you would be basically having a kind of ECB inside your $2n$-block-cipher.
you do not have a full diffusion on your $2n$-block-cipher : if you change a bit in the first part, only that part is modified (orange diffusion on red).

$2n$-Feistel construction

However if you meant to use that $n$-block-cipher as $F$ in your Feistel $2n$-block-cipher, then you will have to make a sufficient number of rounds (at least 4 to get full diffusion : see p. 41). Therefore compared to a parallel CTR encryption method just using that $n$-block-cipher, you are 4 times slower and you don't really have a gain in security in term of key as the space is the same.

Your idea is this : given a $n$-bit block cipher, one can construct a $2n$ bit block cipher using a Feistel construction. More over you want to use 2 keys in order to increase the security margin.

Given enough rounds (at least 4), I can't see any security hole in that construction (but I'm not a cryptographer yet).

$m$-blocks Feistel construction ($m \times n$ bits-block-cipher)

for i in [1 .. number_of_rounds] do
    for j in [1 .. m] do
        subblock[j+1 mod m] ^= E(K[j],subblock[j])

This construction can be displayed as such (e.g. with 5 blocks, 2 rounds)

In order to get a full diffusion you need a strict minimum of 2 rounds.
However this is the same as using the $n$-cipher as a keyed $S-box$. By the way, the more blocks you add, the closer you are to a SPN.


Does adding more letters provide added security compared to a standard substitution cipher?

If I understand you correct you mean with "standard substitution cipher" one which has a mapping from one letter to a specific other letter with case being ignored (mapping 26 to 26). And your improved version would map one letter to another letter with case not being ignored (mapping 52 to 52).

This would only be a very marginal improvement if at all. Given how words are structured (upper case almost only at the beginning) the necessary search space could be easily reduced to find out which target characters are mapped from lower case and which from upper case characters. The rest of the analysis can stay the same, i.e. looking for for characters and character combinations which are more common in the original language and mapping these to similar repetitions in the cipher text and thus quickly reversing the mapping.

In short: the system stays broken even if marginally improved.


Proof that this is not a secure pseudorandom function?

Hint: multiplicative property.

What you have tried does not work because $y_1=y_2$ does not hold in general when $x_2=y_1+p$ (further, adding $p$ is identity in $Z_p$ ).

You want to build a distinguisher for $F_k$. Arguably, $F_k(1)=1$ is enough for that, but you can build a more general distinguisher from $F_k(x_1\cdot x_2\bmod p)=F_k(x_1)\cdot F_k(x_2)\bmod p$.


What is the fastest integer factorization to break RSA?

The IEEE paper is silly.

The factorization method they give is quite slow, except for rare cases.  For example, in their table 1, where they proudly show that their improved algorithm takes 653.14 seconds to factor a 67 bit number; well, I just tried it using a more conventional algorithm, and it took 6msec; yes, that's 100,000 times as fast...


Common cyphers where the plaintext is the same length as the cyphertext

Any cipher or cipher mode that implements Format Preserving Encryption (FPE) - by definition.

NIST has created a US standard document called NIST Special Publication 800-38G: Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption. This document lists two modes of operation abbreviated as FF1 and FF3. These are format-preserving, Feistel-based encryption modes. FF1 was previously known as FFX[Radix] and FF2 as BPS.

Stream ciphers or stream cipher modes of operation have the same property, but they have the problem that they require a nonce or IV, which typically has to be send with the ciphertext unless the state is otherwise synchronized between the party doing the encryption / decryption.

ECB and CBC mode have the same property, but the plaintext needs to be a certain number of full blocks and padding should not be applied. ECB is insecure and CBC also requires an IV to be used.

Commonly disk encryption routines have the same property as well, but they may restrict the input to a specific sized chunks. ESSIV for instance uses a hash over the sector number and key to create an IV, sidestepping the issue that CBC requires an unpredictable IV.

So for symmetric ciphers / cipher modes this is a common property except that they often require an IV and sometimes padding. If the ciphertext also needs to authenticated then an additional authentication tag may be required as well.

Asymmetric ciphers commonly have to expand the ciphertext compared with the plaintext to be considered secure. RSA - for instance - could be used to have a ciphertext that is the same size as the plaintext, but the message space would have to be identical to the (randomly generated) modulus, and encrypting the values 0 and 1 would be completely insecure (because the modular exponentiation would not alter the plaintext message).


If the keystream $p$ is as long as the plaintext $x$ (and is not reused), then $y_n := x_n \oplus p_n$ is a one-time pad, which is theoretically unbreakable, and thus needs no further strengthening.

On the other hand, if $p$ is shorter than $x$, then what you have is basically equivalent to a Vigenère cipher, which is known to be quite weak.  Thus, any additional obfuscation may well improve it, although it's still unlikely to produce a truly secure cipher.

It should be noted that your construction is almost general enough to encompass arbitrary synchronous stream ciphers, which are of the form $y_n := x_n \oplus f(p, n)$.  The only difference is that stream ciphers are generally designed (with good reason) so that each byte (or bit) of the output of $f$ depends essentially on the entire key $p$.


Generally accepted standard(s) for key managment?

There are some agreed as universal, but then some might disagree it's generally accepted:

ISO 27001/27002 land, as it's generally accepted standard for data protection, too. It has a section on key management, based around bloody obvious goals: cryptographic keys have to be protected against modification, loss, destruction and leakage. It requires system to have certain procedures around key management:

key generation
certificates of public key generation
key distribution/activation procedures
key storage and authenticated key access
key change procedure
working with leaked keys, key revocation, etc.
business continuity goals (what if revoked keys protected unique data)
... I certainly forgot something here, haven't touched the standard in years, but aforementioned procedures are really important even outside ISO formalism.

NIST has this beautiful document, which can be accounted as a standard in some circles.
Some time ago, I've been asked to write a novice-friendly blog post about typical key management procedures you modern app developer may want to understand. It also somehow outlines the generally accepted standard measures for key management and protection, yet I've tried to make explanations as simple and accessible as possible.


I've got my private key compromised. How does CRL work?

That depends on the concrete CRL.

As long as you have access to your private key, you can sign the revocation request. This prevents anyone without access to the private key from issuing a faked revocation request.

With access to the private key, a faked revocation request can be sent. But in this case the damage is already done, and a revocation is actually helping the victim.


Since you only ask for help on your class assignment, I will not give you the whole answer, but will hopefully point you in the right direction.

You are able to decrypt any ciphertext you want, but only have time to decrypt 128. Let's think about this from another perspective. What if you already knew exactly what ciphertext you wanted to decrypt. Say the ciphertext is 126 zeros, followed by two ones (I'll denote this mathematically as $0^{126}11$). You could just ask for the decryption of that, easy enough.

How could you get the decryption of it, given the decryptions of $0^{127}1$ and $0^{126}10$?


Tinyec only supports Weierstrass curves, with an equation of the form $y^2 = x^3 + a x + b$. Curve25519 is a Montgomery curve, with an equation of the form $B y^2 = x^3 + A x^2 + x$. Tinyec's arithmetic can't do Curve25519 since its $A$ parameter is nonzero.
It would be less work to adapt Scapy-ssl_tls to one of the existing interfaces to Curve25519 than to write Montgomery curve arithmetic yourself.


Verify authenticity of TLS/HTTPS communication

Your assumption is correct; after the initial key exchange, everything is done with symmetric encryption.  As the client has the symmetric keys, he can create any transcript he wants, and figure out how it would be encrypted and integrity protected.

TLS was designed to do secure communication; nonrepudiable transcripts were never a design goal.


ElGamal digital signature. why mod p-1 in delta?

Basically because of Fermat's little theorem: if $a$ is not divisible by $p$ then $a^{p-1} = 1$ $mod$ $p$. A part of the expression for $\delta$ appears as a power of $a$ in the ElGamal signature verification equation, which "happens" to work because it is reduced modulo $p-1$ so Fermat's little theorem applies.


Creating your own encryption and decryption algorithm

Edit: how to break Vigenère
Yes, this cipher (which as SEJPM points out, is Vigenère) is vulnerable to frequency analysis, but Vigenère resists this a bit, because common letters don't always get ciphered into the same ciphertext. The unavoidable vulnerability stems from the repeating nature of the key.
Let's say your message is $N$ characters long and your key is $k$ characters long. You may think that by repeating the key until you reach $N$ characters that you gain some "units of security" ("it's $\lfloor N/k \rfloor$ times more secure!"). But if I know your message is enciphered in this way, I have learned a great deal about your plaintext.
If I can estimate your key length $k$ $-$ and I can, with the great Kasiski's help $-$ then I can take every $k$th ciphertext character and group them together (for example, if $k=5$, group together the first, sixth, eleventh, etc. characters, then group the second, seventh, twelfth, etc. into another block, and so on). Each block is enciphered with the same character, a character from your key. At this point, a straightforward frequency analysis comes into play; breaking this is no harder than breaking the Caesar cipher you started with.
I do this for each "group" and now I have recovered your key.

It is cool that you came up with the idea of a polyalphabetic cipher on your own. But as the comment and other answer have pointed out, this cipher is insecure and can be broken quite reliably. Seriously: only use this for fun or pedagogical reasons.
In 1863, Kasiski even knew how to guess the length of the key for this cipher! That forces you to make your key longer / harder to remember.
It's very efficient; you can encipher text quickly with it. But that's a double-edged sword: I can attempt to decipher it quickly as well.


Finding a secret key corresponding to a public key

The expected time to compute a secret key from a public key is of course entirely dependent on the scheme and the security parameter. Of course for the scheme to be secure, the probability that an adversary can make such computation in poly time must be negligible.

Regarding your second question, you might want to look here.
Again this is entirely dependent on the scheme.


Trouble understanding range proof of Greg Maxwell's Confidential Transaction

not sure if I understand your problem.
But the zero commitment means that you know some k that makes k*G= your commitment C.

If you sign something with C as the public key, it also means that you know k.

so,
if you can sign with C = zero commitment with C.

Hope it answers your question.


Storing private keys directly in a keyring

Is there a good reason not to store the private keys directly in a properly encrypted user keyring?

maybe generic answers what are you looking are standardization and platform independence. When writing software, we (mostly) need to take care that it will eventually running on all platforms. PKCS#8 is widely accepted standard usable everywhere.

What can be important here is the context. Are the keys directly used by user (to decrypt/sign something) or by machine (service)?

When we consider the end-user context, I agree with Maarten's comment, IMHO the best option is to have the keys on hardware. (Any reasonable crypto-device is often exposed as PKCS#11). Otherwise there is no advantage of Keyring over other keystores (ok, it can be integrated with UI such as Gnome)

When using the keys from the services, PKCS#8 is well supported and widely accepted standard, so it works everywhere. And the private key may be encrypted, but the decryption key needs to be available somewere too for server side services.


Byzantine Agreement: Why does OM need f+1 rounds in a synchronous setting?

I will use $m$, not $f$  according the original paper.  It gets an Byzantine agreement in $m+1$ rounds.

The paper the byzantine generals problem       says:

  THEOREM 1. For any m, Algorithm OM (m ) satisfies conditions IC1 and IC2
  if there are more than 3m generals and at most m traitors.

Since it is a recursive algorithm,
from  $OM(0)$ to $OM(m)$, so it is $m+1$ rounds.


Given $g,g^t$ in an RSA group modulo $N=pq$, is it hard to compute $g^{t^{-1}}$?

I know that I am not exactly answering your question, but I am pointing you in a potentially interesting research direction. Your question is not standard in the area of discrete log and Diffie-Hellman problems since you are considering a cyclic group of order $p\cdot q$ where $p$ and $q$ are primes. (Typically, we like looking at group of prime order.)

Your question is actually asking whether you can reduce this problem to solving the discrete log problem. I don't have any answer to that, but it reminds of an old paper by Biham, Boneh and Reingold that shows that the Diffie-Hellman problem modulo $N=pq$ (for Blum integers) is actually equivalent to factoring. This isn't the same thing, but there's something similar. The paper is here: https://omereingold.files.wordpress.com/2014/10/cgdh.pdf.


Elliptical Curve Cryptography decryption resulting point at infinity?

Summarizing the answer from the comments, starting with poncho:

  Since point $(27, 40)$ and $(27, 3)$ is a straight line, it will resulting
  point infinity.'; actually, not. $(27,40)−(27,3)=(27,40)+(27,40)$, that
  is, we have a point doubling...

which resulted in

  how can $(27, 3)$ can turn to $(27, 40)$ and not $(27, -3)$?

which is resolved by user94293

  $(27,40)$ and $(27,−3)$ represent the same point. Computations are done in
  $\mathbb F_{43}: −3\bmod43=40$


Password derived hash to encrypt known plaintext as password check

To be entirely honest the Idea is pretty intresting but wouldn't help a lot. AES is, mainly because it's widely used, a pretty cheap thing to do, so there's basically just one step more after hashing, so it wouldnt make a lot of a difference in that part. but one thing that I think may be intresting would be (but for a different reason):

Not encrypting a static String, but rather use the hash to create or encrypt a random Private Key generated while the user is signing up, while keeping the Pubkey readable and offer it to the user.

If you now use that specific key to sign something (similar to a canary report) and the user can check that it was signed with his key, then he can be relatively sure that for example no password reset happened because one cant reset the password without resetting the keys.


how the symmetric and asymmetric encryption are used in the SET protocol?

As per section 3.2 (which goes into further detail) of the SET specification here:
Symmetric Encryption

SET will rely on cryptography to ensure message confidentiality. In SET, message data will
be encrypted using a randomly generated symmetric encryption key. This key, in turn, will
be encrypted using the message recipient’s public key. This is referred to as the “digital
envelope” of the message and is sent to the recipient along with the encrypted message itself.
After receiving the digital envelope, the recipient decrypts it using his or her private key to
obtain the randomly generated symmetric key and then uses the symmetric key to unlock the
original message.

Asymmetric Encryption

SET uses a distinct public/private key pair to create the digital signature. Thus, each SET
participant will possess two asymmetric key pairs: a “key exchange” pair, which is used in
the process of encryption and decryption, and a “signature” pair for the creation and
verification of digital signatures. Note that the roles of the public and private keys are
reversed in the digital signature process where the private key is used to encrypt (sign) and
the public key is used to decrypt (verify the signature).

You can find even more detailed information in the Formal Protocol Definition here which also goes into some detail on PReq messages (on PDF page 84).


Security of the Goldreich–Goldwasser– Halevi (GGH) Scheme

If you look at the GGH paper, they explicitly say that they reduce to a random instance of CVP. At the end of the paragraph on CVP in Section 2.1, it explicitly says: "As we explain in Section 3, an attack against our trapdoor function amounts to finding an exact solution for some random instance of CVP." Peikert is referring to worst-case guarantees (i.e., hardness for any instance of CVP) whereas GGH considered an average-case problem (when the instance is generated at random).


Why does the NIST Runs Test include a Frequency Test?

The Monobit test checks the frequency of 0 and 1 over the whole sequence tested. The Frequency test does that on $M$ sub-blocks, where $M$ is an additional parameter. For example, with $M>1$ (and way up), a sequence of $n=8000000$ bits consisting of $4002000$ times 0 followed by $3998000$ times 1, which passes the Monobit test, will fail the Frequency test.

Such detailed examination of the justification of each test should not obscure the big picture: only failing SP-822 (or any statistical test of randomness) matters. SP-822 is good at what it does, but passing a statistical test does not prove anything useful from a cryptographic standpoint. When a generator fails SP-822, the generator is flawed. Don't fall to a converse error!
It's impossible to assess positively the quality of a conditioned¹ random source from its output alone (as SP-822 proceeds). That's a trivial consequence of the existence of practically secure PRNGs. And SP-822 is not applicable in practice to unconditioned random sources (for one thing, they tend to fail the Monobit test. Those that do not for long sequences have some internal de-biasing, which amounts to conditioning).
Remember, Dual_EC_DRBG was developed with the purpose of having a backdoor in crypto gear, and phased out when that got widely known. Meanwhile, Dual_EC_DRBG had become a standard, and people tend to trust standards. A RNG using Dual_EC_DRBG passes SP-822 with flying colors. SP-822 is a de-facto standard on randomness testing. That test and Dual_EC_DRBG are developed by the same organization. I do not make a certain conclusion on intention. Draw your own.

Actual security evaluation of cryptographic random generators should assess:

The physical soundness of the unconditioned random source.
The statistical soundness of an online test that monitors that source on the field, and safely shuts the whole thing off on failure. Principles of the simplest tests of SP-822 apply.
The cryptographic soundness of the conditioning algorithm.
The conformity of the implementation to the above design.

¹ The traditional structure of a RNG comprises a source of randomness followed by conditioning that produce the final output, plus supervision to detect failure. Some classic conditioning techniques include Von Neumann Extractor; LFSR in scrambler mode followed by decimation; and various CSPRNGs.


Assuming that it's sufficient to catch a cheating player after the round is over, this seems trivial to implement using only bit commitments.

Let $\mathsf{Com}$ be a bit commitment scheme.

At the beginning of each round:

Each player  $P_i$ chooses a random index $j\gets \{1,2,3,4\}$, computes
$$
c_i^k := \begin{cases}\mathsf{Com}(0)&\text{if } k\neq j\\ \mathsf{Com}(1)&\text{if } k= j\end{cases}
$$
for $k\in \{1,2,3,4\}$, and publishes $(c_i^1,c_i^2,c_i^3,c_i^4)$. These commitments represent their randomly shuffled cards.

**Placing cards:*
Whenever a player wants to play a card, they simply broadcast an index $k$. This signifies that they placed the card represented by $c_i^k$.

Flipping cards:
When the player who won the challenge wants to flip a card, the player who played it simply opens the corresponding commitment.

Once the game has concluded, everyone opens all of their commitments and it can be checked that they indeed committed to exactly one $1$ and three $0$s.

If you want to catch cheating players immediately, you can add a non-interactive zero knowledge proof to the first message, pricing that the commitments are to exactly one $1$ bit and three $0$s.

The hiding property of the commitment scheme should prevent anyone from knowing any (but their own) placed cards, while binding prevents players from opening cards they did not play.


Can I use `SHA (message || key)` as MAC?

If you know a length-preserving collision, that is, two distinct messages $M_1, M_2$ of the same length with $\operatorname{SHA}(M_1) = \operatorname{SHA}(M_2)$, then you know apriori that two messages $M_1 || \text{Pad}(M_1)$ and $M_2 || \text{Pad}(M_2)$ (where $\text{Pad}$ is the SHA padding function) will evaluate to the same value (and hence the MAC is broken).

This immediately shows that this MAC is insecure if instantiated with SHA-1.


X3DH Protocol - How can the receiver calculate the Shared Key?

Alice uses Alice's private keys and Bob's public keys.

Bob uses Bob's private keys and Alice's public keys.

The notation DH(A, B) means that you combine whichever private key you know between A and B with the public key of the other.  So, when Alice computes DH(IKa, SPKb), she uses the private part of her long-term identity key IKa and the public part of Bob's signed prekey SPKb; when Bob computes it, he does it the other way around.


Which hash function to be used with DSA 2048

This is reasonable and gets at most of it.

One critical limit of DSA with a 160-bit prime group is that you can't get better than 80-bit collision resistance by the birthday bound.  You really want a uniform random function from whatever is your finite message space to $\mathbb Z/q\mathbb Z$, but that's a pain to achieve, so you might choose a $\lceil\lg q\rceil$-bit hash function like SHA-1—but SHA-1 is known not to be collision-resistant at the maximum possible 80-bit security level in the circumstances.

You might be concerned about the small modulo bias of reducing a uniform random integer in $\mathbb Z/\lceil\lg q\rceil\mathbb Z$ modulo $q$.  You might be concerned about security against multi-target attacks.  If you are concerned about that, then you might choose a double- or 1.6-size hash like SHA-256 or BLAKE2s, and attain collision resistance up to the maximum possible 80-bit security level.

For a loose comparison, a double-size hash, SHA-512, was chosen for Ed25519's ~256-bit group, for several conservative reasons.  Now, the comparison is not precise, because Ed25519 is a qualitatively different signature scheme—and superior in pretty much every respect, except compliance with US government standards, to DSA: it uses the hash in a different way so it doesn't even rely on collision resistance, it doesn't break catastrophically and barf out your private key if you use it on a machine with a broken RNG, it's faster and smaller, etc.


Do Curtmola et al.'s IND-CKA1/2 security definitions protect against search pattern leakage?

The condition $\tau(\mathbf{D}_{0}, w_{0,1},\ldots,w_{0,q})=\tau(\mathbf{D}_{1}, w_{1,1},\ldots,w_{1,q})$ rules out the possibility that $\mathcal{A}$ issues the keywords as I pointed in the question, since the output of $\tau$ includes the search pattern matrix defined in page 9. This has the effect of weakening the definition to allow search pattern leakage.

As a note, the stronger definition in Shen et al.'s 1 does not include a restriction of this type, and so it captures the search pattern protection property.

1 Shen, Emily, Elaine Shi, and Brent Waters. “Predicate Privacy in Encryption Systems.” In Theory of Cryptography, edited by Omer Reingold, 5444:457–73. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2009.


What are good sources for properly learning cryptography for a mathematician?

Reference requests are off-topic here, so your question will likely be closed. Nevertheless, here are three pretty good introductory books that don't skimp on mathematical details. They're all intended for grad students with a good amount of mathematical maturity.

Foundations of Cryptography volume 1, by Goldreich. This is the classic book in what I sometimes think of as "complexity-theoretic crypto", which starts with one-way functions (OWFs) and builds more complex primitives like pseudorandom generators and zero-knowledge proofs from OWFs. Another (soon-to-be-published) book of this type is Pass and shelat's "A Course in Cryptography"; you can google around for the most recent version.
Introduction to Modern Cryptography by Katz and Lindell. This is a newer book that covers what most people consider "applied cryptography" - that is, how do you build an encryption scheme that you would really implement to protect some data. Books in this genre generally start with the one-time pad instead of OWFs. Covers the basics of symmetric- and public-key cryptography well, but does not cover zero-knowledge proofs.
A Graduate Course in Applied Cryptography, by Boneh and Shoup. A draft of a not-yet-complete book on applied cryptography. The finished chapters cover a fairly large subset of what Katz/Lindell does, and some subjects (e.g. constructing PRFs) in more detail. Also has a lot of nice exercises and neat "case studies" on topics like side channels.

Because someone suggested it in a comment: I would avoid more specialty texts that only cover the mathematics of public-key crypto, at least for your first text. This includes Hoffstein et al.'s "...mathematical cryptography" and Koblitz's books. These are good books, but they'll only teach you enough modern cryptography (i.e. security reductions and definitions) to be dangerous. Learn how to do a proof by reduction and understand security definitions before you get into the deep mathematics of public-key cryptography.


Is the one-more discrete log problem hard in the Generic Group Model?

Yes, this was shown in a recent work of Coretti et al [CDG].  Loosely speaking, the lower bound states that an adversary that makes at most $T$ queries to the GGM oracle succeeds with probability at most $T^2/N$, where $N$ is the size of the group. They in fact consider a stronger model where the adversary is allowed arbitrary pre-computation in the GGM. See §5 for more precise statements and Table 2 for a summary of their results.
[CDG]: Coretti, Dodis and Guo, Non-Uniform Bounds in the Random-Permutation, Ideal-Cipher, and Generic-Group Models, Crypto'18


How to decrypt / break enigma-encrypted ciphertext with given configuraton?

If you know the configuration of the machine you can easily decrypt the message. All you need is an enigma machine, I found one of several emulators online: Enigma emulator.


Decrypt simple CBC message with known IV using XOR encryption

That's easy: $C_1 = K \oplus (M_1 \oplus C_0)$. You know $C_1$, $M_1$ and of course $C_0$, the IV. You can easily rewrite this as $K = C_0 \oplus C_1 \oplus M_1$.

What is left is simply decryption with $K$. In case of XOR encryption, decryption is the same as encryption, so $M_i = (K \oplus C_i) \oplus C_{i-1}$.

Notes:

XOR is associative and commutative, so you can leave out the parentheses in the formulas and rewrite the formulas like I did above.
this will obviously not work with secure block ciphers since retrieving $K$ is not supposed to be possible, even when given a known plaintext / ciphertext pair.


Encrypt a file with AES using a secret key derived with Argon2

Which of the two types of Argon2 is the best for password-based key derivation?

In short, as said by draft-irtf-cfrg-argon2-03;

  If you do not know the difference between  hem or you consider side-channel attacks as viable threat, choose Argon2id.

Argon2d is faster and uses data-depending memory access. Data dependency immediately enables side-channel. This is suitable for cryptocurrencies and applications with no threats from side-channel attacks.
Argon2i uses data-independent memory access and this is preferred for password hashing and password-based key derivations.
Argon2id In the first half of the first iteration works as Argon2i and for the rest works as the Argon2d. This enables both side-channel protection and time-memory trade-off.

  How can I use Argon2 with a predefined salt?

From a library for Argon2

    Usage:  ./argon2 [-h] salt [-i|-d|-id] [-t iterations] [-m memory] [-p parallelism] [-l hash length] [-e|-r] [-v (10|13)]
            Password is read from stdin
    Parameters:
            salt            The salt to use, at least 8 characters
            -i              Use Argon2i (this is the default)
            -d              Use Argon2d instead of Argon2i
            -id             Use Argon2id instead of Argon2i
            -t N            Sets the number of iterations to N (default = 3)
            -m N            Sets the memory usage of 2^N KiB (default 12)
            -p N            Sets parallelism to N threads (default 1)
            -l N            Sets hash output length to N bytes (default 32)
            -e              Output only encoded hash
            -r              Output only the raw bytes of the hash
            -v (10|13)      Argon2 version (defaults to the most recent version, currently 13)
            -h              Print argon2 usage

The libraries handle this for you. You just provide a random salt and store it, if you want to get the same result again, use the same salt.

  Is there a point in using a salt that is freely accessible (if my data are stolen)?

Normally, you can store these values - salt, iteration, memory usage, parallelization, output size - with your data. If you really want to keep them separately from the storage you can do it, but there is no need. It is designed to be secure even if they are known by an attacker. When servers are attacked, all of these parameters are also acquired by the attackers. Salt is used against rainbows tables. Remember Kerckhoffs's principles, only the key is secret.

  can somebody shed light on how Argon2 can be used as a password-based key derivation function?

There is a Key Encryption Key (KEK) methodology that is common with disk encryption utilities. Let say a file encryption key (FEK) is randomly generated by a good random source. Then your strong password is used to derive the KEK by a KDF, here in your case Argon2id.
$$\text{KEK} = Argon2id(salt, password)$$
Use your KEK to encrypt FEK and store it on your target ( your computer or phone). $$FEK^* = AES\hbox{-} Enc_{KEK}(FEK)$$

Now, you want to encrypt a file, use your strong password to generate the KEK

$$\text{KEK} = Argon2id(salt, password)$$

and use the KEK to decrypt your FEK from the storage.

$$FEK = AES\hbox{-} Dec_{KEK}(FEK^*)$$

Encrypt the file with an authenticated encryption mode like AES-GCM or ChaCha20-Poly1305 and store it on your computer or cell-phone.

$$\text{EnryptedFile, ATag} = AES\hbox{-} GCM\hbox{-}Enc_{FEK}(\text{file})$$ where ATag is the authentication tag.

You need to keep FEK only in system memory and purge it when the operations are finished.

The benefits of this approach;

you only need to memorize your strong password
The Encrypted FEK and Argon2id parameters can be stored together with the files or some other suitable place for your choice.
For each file, you can generate a new random FEK.

  always uses a random salt for hashing".

It is for each file or password not for every run of Argon2 run. You need to derive the same results if you want to compare the hash of the file or generate the same key, you have to use the same parameters including the salt. And to not forget that salt, you must write it somewhere.


Any problems with this secure time synchronization scheme?

Yes, this is a perfectly secure solution.

The principle drawback is that the precision available is limited by the round-trip time to the trusted time server.  If the trusted time server is 50ms away (i.e., 100ms round-trip time), which is a plausible situation that might arise in real life, then you cannot synchronize the client's time to within a guaranteed precision of better than $\pm$ 50ms (or so).  If this is adequate for your purposes, then yes, this is a fine solution.  If this is not enough precision, then you have a harder problem, and I'm not sure whether there's anything you can do in the presence of an active adversary.

Despite what has been claimed in the comments, the nonce is essential to security (otherwise a man-in-the-middle could trivially break the protocol).  Keep the nonce.  Do not remove it.  I think you know all that already, just re-emphasizing it for clarity.


What's the downside of using X.509 in SSH instead of PKI

The fundamental difference is in how (and wether) the clients and servers identity is validated.

In X.509, keys are authenticated by virtue of being issued by a trusted certificate authority. That makes it easy to use when the client starts out knowing nothing about the server's identity, and the server does not need to know anything about the client's identity. But can be a particular nightmare to manage when the client also needs to authenticate against the server.

In SSH, keys are self-generated (similar, although not the same, to self-signed X.509 certificates), and are authenticated by relying on a fingerprint, which has to be transmitted out-of-band. That makes it easier to use in scenarios where both ends are reasonably trusted. SSH also has built-in mutual authentication. The client verifies the server's identity by its host key (what a server X.509 does in TLS), and the server verifies the client's authority through the entry in the authorized_keys file (that's the equivalent of X.509 client certificates).

SSH is mostly used for internal communications within an organization, where both ends are, at least somewhat, trusted. The overhead of generating and distributing X.509 certificates would put a serious burden on many use cases (just think of spinning up test servers on a daily basis in a development environment!).

It is also designed to not rely on the destination name (so you can use the DNS name most of the time, and IP addresses if your DNS system fails for some reason).

That said, you can actually configure SSH to use X.509 certificates. As far as I understand it, though, it only uses the public and private keys, and ignores the rest of the certificate.

And you can also get most of the benefits of an X.509 certificate with SSH by adding an SSHFP record to your DNS (this is non-trivial as you first have to enable DNSSEC). With an SSHFP record, one could argue you are actually in better shape than with an X.509, because you get the benefit of an authenticated host key, without relying on the somewhat broken certificate-authority trust model.

Bottom line: The SSH mechanism and X.509 are designed for different scenarios. Both are reasonably secure in their respective niches.


Problem in Identifying relevant documents to evaluate Precision in Information Retrieval (IR) Systems

Yes, the client needs to figure out which of the results are actually relevant. For obfuscation reasons the server returns irrelevant documents and also cannot know which documents are irrelevant so the client has to make that distinction.


I have seen that used in the context of session keys, to describe how a key is tied to an identity without any certificate relative to that key could only be known by another identified party, without assurance that this party ever held that key.

For example, one generates a random symmetric key, encrypts it using (say) RSA and a public key, and sends the cryptogram to the alleged owner of the public key. Because only knowledge of the associated private key allows to recover the symmetric key, that symmetric key can only be known by the one that generated it and by the rightful holder of the asymmetric key, but it is not yet known if this rightful holder actually knows that symmetric key. There is thus implicit authentication of that symmetric key.

That key can later be used to demonstrate integrity and origin of a message from the holder of the asymmetric key to the originator of the cryptogram that established the symmetric key, using a MAC. As a side effect that demonstrates knowledge of the symmetric key by that rightfull holder, boosting its status from implicit to explicit authentication.

That usage occurs, for example, as "implicit key authentication" in the Key Authentication section of the Encyclopedia of Cryptography and Security, first edition. This is not a recommendation for this book, which I'm seldom using.

Update: reading that reference, I have pretty much turned around my definition. An encyclopedia is useful, sometime.


Linear feedback shift register combination, secure?

I think Trivium, and ChaCha20 are excellent choices.

If you insist on using the shrinking generator or the self shrinking generator, you should use them without hiding the polynomials, which would be security by obscurity. I'd suggest that the SSG is probably stronger than the SG, for given keylength. But there are fast correlation and guess and determine attacks on both, so your real strength is only a fraction of the keylength. This would mean using at least 256 bit length LFSRs.

Finally they haven't been designed with modern Key/IV based operation. Key/IV based operation would help you achieve the goals you might have in mind for the question of whether you should change key and/or the secret polynomial.


I think you are looking for "mental poker".
Here is a video of Ron Rivest specifically discussing how to deal cards via mail/internet.
The paper here might also be a good read (from the creators of RSA).


Question about Enigmas involutional property and its reduction of possible ciphers

The number of involutions of size $n$ satisifies the recurrence relation:

$$I(n) = I(n-1) + (n-2)I(n-2)$$

(This recurrence is easy to deduce).

Given than $I(1) = 1$ and $I(2) = 2$, we can easily compute $I(4) = 8$, which is strictly smaller than the number of permutations of size 4 (which is 24).

This recurrence allows us to quickly compute the number of involutions of size 26 as 158,432,124,870,784; much smaller than the number of permutations 26! = 604,937,191,689,908,372,404,961,280

BTW: the involutions of size 4 are:

$$ABCD$$

$$ABDC$$

$$ACBD$$

$$ADCB$$

$$BACD$$

$$BADC$$

$$CBAD$$

$$CDAB$$

$$DBCA$$

$$DCBA$$


Strict Avalanche Criterion and Avalanche criterion?

The definition of avalanche effect is given in the paper of Webster, A. F. "On the design of S-boxes". Advances in Cryptology - Crypto '85 as :

  For a given transformation to exhibit the avalanche effect, an average of one half of the output bits should change whenever a single input bit is complemented.

It is also seen as each bit should have 50% chances to change if you change 1 bit of the input. (strict avalanche)

In the avalanche criterion you look at the output as a whole (average 50% of the bits changes).

In the strict avalanche criterion, you look at each bit one by one and you verify that what ever the other bits will change, it will have a 50% probability to switch.

Related questions:

Hash functions and the Avalanche effect
Calculation of the avalanche effect coefficient


Based on the additional details in the comments, it seems like your question is: given $c_1=a\oplus d$ and $c_2=b\oplus d$, can we get $(a+b)\oplus d$. Where $a,b,d\in\mathbb{Z}_p$, $+$ is addition modulo $p$, and $\oplus$ is a bitwise XOR of the values, then taken modulo $p$.

Or put another way, is there an operation $\boxplus$, such that $(a\oplus d)\boxplus (b\oplus d)\equiv (a+b)\oplus d\bmod{p}$?

Hopefully I've understood the problem correctly.

The answer is no, except in the trivial case of $p=2$, or more generally (if $p$ is not necessarily a prime) when $p=2^q$ for some prime $q$. That is because in these two cases, in the finite field $\mathbb{Z}_p$, $\oplus$ and $+$ are traditionally the same operation (note that by $+$ I am not talking about integer addition modulo $p$, I am referring to addition in the finite field). Or put another way $+$ is defined as bitwise xor in these fields.

In the case where $p\neq 2$ and $p\neq 2^q$ for some prime $q$, the bitwise XOR destroys all algebraic structure necessary for there to be an operation $\boxplus$. Now, what you can do is use $+$ instead of $\oplus$. Then you have $(a+d) + (b+d) = (a+b) + (d+d)$ and to decrypt, subtract $(d+d)$. If doing this, you should use different $d$ values for each message. In other words $(a+d_1) + (b+d_2) = (a+b) + (d_1+d_2)$ and to decrypt, subtract $(d_1+d_2)$. The $d_i$ values must be randomly chosen.

Full disclosure: My answer is based on intuition. It might be hard to prove that $\boxplus$ does not exist, but it seems very unlikely that it does. Basically we need associativity between $\oplus$ and $\boxplus$ (i.e., $(a\oplus b)\boxplus c = a \oplus (b\boxplus c)$ and $\boxplus$ must be commutative ($a\boxplus b = b\boxplus a$). There are lots of candidates for commutativity, but I can't think of any for that type of associativity.


How is it possible that $g^q \equiv 1 \pmod p$ for a generator g?

You are probably getting confused with the meaning of "generator" here. You are correct that a generator for the entire multiplicative group modulo $p$ cannot satisfy $g^q \equiv 1$ by definition.

However - assuming $k = 2$ here - what you probably read is that $g$ is the generator of the quadratic residues modulo $p$, and this group has order $(p - 1)/2$. A generator $g$ for that group is, obviously, a quadratic residue, meaning it is of the form $g = a^2 \pmod{p}$ for some group element $a$, and therefore must satisfy $g^q \equiv 1 \pmod{p}$, since $g^q = (a^2)^q = a^{2q} = a^{p - 1}$.

Does that clear it up?


For elliptic-curve-based protocols, it is assumed that finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point is infeasible: this is the "elliptic curve discrete logarithm problem" (ECDLP). The security of elliptic curve cryptography depends on the ability to compute a point multiplication and the inability to compute the multiplicand given the original and product points. The size of the elliptic curve determines the difficulty of the problem.

We can formally define an elliptic curve (over a field k) is a smooth projective curve of genus 1 (defined over k) with a distinguished (k-rational) point. However, not every smooth projective curve of genus 1 corresponds to an elliptic curve, it needs to have at least one rational point. The definition of the elliptic curve also requires that the curve be non-singular. Geometrically, this means that the graph has no cusps, self-intersections, or isolated points.

There is an infinite number of elliptic curves, but a small number that is used in elliptic curve cryptography (ECC), and these special curves have names. Apparently there are no hard and fast rules for how the names are chosen, but there are patterns. IETF has published a report on the list of alternate elliptic curve representations recently. You can refer to the IETF report here. Following are some of the reference elliptic curve families. A few of them are missing in the diagram.

Curves in short Weierstrass form
Montgomery Curves
Twisted Edwards Curves
Supersingular Edwards Curve
Hessian Curve
Twisted Hessian Curve
Jacobi Quartic Curve
Doubling-oriented Doche–Icart–Kohel Curve

Elliptic Curves were originally written in Weierstrass form. Edwards elliptic curves have their own advantages: addition, doubling and tripling can be done faster on Edwards curves than on curves given by a Weierstrass equation. This is because the addition law on Edwards curves does not have exceptions, while the addition on Weierstrass curves
distinguishes several special cases.  The Montgomery curve is suggested for application in elliptic curve cryptography because arithmetic in this curve representation is faster and needs less memory than arithmetic in standard Weierstrass form.

Please find an insightful article on the names of some the prominent elliptic curves used in cryptography.


Is a composition of clocked entities a clocked entity in the UC model?

When you compose $2$ interactive systems $\mathcal{IS}_1$ and $\mathcal{IS}_2$ into $\mathcal{IS}_1 \circ \mathcal{IS}_2$, the book indicates that you're simply connecting the matching ports between them.

In your example $\mathcal{IS} \circ D$ is a clocked entity because when $B$ calls $D$ then $D$ makes a recursive call to $\mathcal{IS}$ by sending the token to $C$. Taking from the book: "When it is clocked it must eventually
return the activation on the matching outport leak" not immediately.

Regarding your second question:

You can think of a synchronous execution as a single thread program execution which goes from one line to the next one. Each line represents an agent and the clock can be here the line number. The clock is just a flag to capture which agent is running at a given time.


The computational complexity of discrete log

The paper you mention actually does contain most of the answers at least as far as “heuristic complexity” is concerned (newer results improve the complexity bounds given in that paper in some parameter ranges, but not the ranges you are asking about). Note that the complexity of the discrete logarithm problem is usually given for a random $x$ (with respect to an arbitrary generator of $\mathbb{F}_q^*$), so the bit length of $x$ doesn't really come into play.

So the best known algorithm for discrete logarithms in $\mathbb{F}_q^*$ when $q$ is a random-looking prime is the general number field sieve (GNFS), which has a heuristic complexity of $L_q[1/3,\sqrt[3]{64/9}]$, where $L_q[\alpha,c]$ is a short-hand notation for $\exp\big((c+o(1))(\log q)^\alpha(\log\log q)^{1-\alpha}\big)$.

Still in the prime case, when $q$ has a special form (which roughly means that it can be expressed as the value of a polynomial with small coefficients at a small integer: think e.g. of a Mersenne prime), one can use the special number field sieve (SNFS) instead, and complexity drops down to $L_q[1/3,\sqrt[3]{32/9}]$ (so one can solve the problem for $q$ of roughly twice the bit size as for SNFS).

As for the case of $q=2^k$, the best asymptotic complexity is provided by Barbulescu et al.'s version of the function field sieve (FFS), which in that case runs in heuristic quasipolynomial time $2^{O((\log k)^2)}$.

All of these complexity estimates depend on heuristic assumptions of the form “such and such family of integers/polynomials contains roughly as many smooth elements as random integers/polynomials of the same size”, so making them entirely rigorous is probably hopeless. In practice, though, they work as advertised (extensive experiments support the estimates in most cases).

Oh, and as a final note, you can probably deduce from the above that the answer to the question of whether the discrete log problem is easier in some fields than others is yes. Basically, for a field $\mathbb{F}_{p^k}$ with $p$ prime, the complexity will depend on the relative sizes of $p$ and $k$ (this is the distinction between the small prime, medium prime and large prime cases of the discrete log discussed in the paper of Joux et al.), and to a lesser extent on whether $p$ has a special form in the sense alluded to above.


Can you help me understand this pseudo random generator example?

Assuming your question is whether $G(x_1,x_2,...,x_n) = x_1,x_2,...,x_n, x_1 \oplus x_2 \oplus x_3 ... \oplus x_n$
is a PRG.

$D$ is some fixed probabilistic polynomial time distinguisher.

So to prove that $G(.)$ is a PRG, you need so show that for all such distinguishers, $D(G(.))$ cannot be distinguished from $D(.)$.

e.g.
$\big| Pr[D(G(s))=1] - Pr[D(s)=1] \big| \leqslant negl(n)$ where $s \leftarrow \{0,1\}^n $

Conversely to show $G(.)$ is not a PRG you simply need to identify a distinguisher $D(.)$ such that the above equation does not hold.

In this case, $G(.)$ looks like it could be distinguished from a random distribution, since the output is just the input, followed by the xor of the inputs.

i.e. $D(.)$ is some function which outputs $1$ if the final bit of output is the xor of all of the previous bits. This would be true half of the time applied to a random distribution, but would always be true for $G(.)$. This would mean that $\big| Pr[D(G(s))=1] - Pr[D(s)=1] \big| = \big| 1 - 0.5 \big| = 0.5$

Since a half is not negligible we can say that $G(.)$ is not a PRG.


Non-cryptographic hash function as MAC for stream ciphers

If I understand you correctly, you want to use $C = \mathrm{Enc}_{K,N}(m || \mathrm{hash}(m))$ as authenticated encryption. This is a bad idea, even for cryptographically secure hashes.

Consider an attacker who knows your plaintext $m$ and wants to replace it by $m^\prime$. He calculates $C^\prime = C \oplus (m || \mathrm{hash}(m)) \oplus (m^\prime || \mathrm{hash}(m^\prime))$ which is the valid ciphertext for $m^\prime$.

We had two related questions: How do unkeyed hash functions (for MDCs) provide security? and Is the encryption of a hash a good MAC?.

As alternatives to hash based MACs, you could consider:

Universal hashing
A bit annoying to implement, but features a security reduction to the security of the cipher.

AES-GCM is one a popular choice, but its performance isn't so great in software without specific instructions(AES-NI&co). With those instructions it's really fast, and it's a standard.
Salsa20-Poly1305 is an alternative. It has a fast implementation in NaCl which avoids timing attacks. Poly1305 can be used with any stream cipher and is fast in software.

SipHash

Fast in software, especially for short messages. It produces 64 bit MACs, which should be sufficient because MACs guard against online attacks. It's pretty easy to implement.

The main issue is that it's rather new and thus hasn't seen much analysis. I would only use it if security isn't super important.


Hash which can be used to verify one of multiple inputs?

What you are looking for reminds me of one-way accumulator functions [1]. Basically, a one-way accumulator permits to prove the membership of an element $x$ to a set $S$ without revealing the actual members of the set. See for example this definition from [2]:

  The most common form of one-way accumulator is defined by starting
  with a “seed” value $y_0$, which signifies the empty set, and then
  defining the accumulation value incrementally from $y_0$ for a set of
  elements $S = \{x_1,···,x_n\}$, so that $y_i = f(y_{i−1},x_i)$, where $f$ is a
  one-way function whose final value does not depend on the order of the
  $x_i$'s. [...] Because of the commutative nature of $f$ ,
  a source can digitally sign the value of $y_n$ so as to enable a third party to produce a short proof for any element $x_i$ belonging to $S$ [...].
  A well-known example of a one-way accumulator function $f$ is the
  exponential accumulator  $exp(y,x) = y^x \mod N$, for suitably-chosen
  values of the seed $y_0$ and modulus $N$. In particular, choosing $N = pq$ for two strong
  primes $p$ and $q$ makes the accumulator function $exp$ as difficult to break as RSA cryptography [1].

Update: Let's see an example using the $exp$ function defined above. Suppose $a$, $b$, and $c$ are inputs, and that $y_0$ and $N$ are chosen properly. Then the accumulator algorithm $H_1$ will do the following:

Compute $s = a \cdot b \cdot c$ and $y = exp(y,s) = y_0^s = y_0^{abc}$
For each element $i$ in the input, compute $y_i = exp(y,1/i) = y^{1/i}$. For example, $y_a = y_0^{bc}$.
Output $z = (y,y_a,y_b,y_c)$.

Now, if you want to check if some element $x$ belongs to the original collection, you just have to check if for any of the partial results $y_i$, the equation $y = exp(y_i,x)$ holds. For example, if you try with $a$, then equation $y = exp(y_a,a)$ holds, since $exp(y_a,a) = (y_a)^a = (y_0^{bc})^a = y_0^{abc} = y$. On the contraty, if you try with $d$ different to $a$, $b$ and $c$, then none of the equations hold.

The problem with this solution is that output $z$ grows linearly with the size of the set of members.

References:

[1] Benaloh, J., & De Mare, M. (1994, January). One-way accumulators: A decentralized alternative to digital signatures. In Advances in Cryptology—EUROCRYPT’93 (pp. 274-285)

[2] Goodrich, M. T., Tamassia, R., & Hasić, J. (2002). An Efficient Dynamic and Distributed Cryptographic Accumulator*. In Information Security (pp. 372-388).


Is there an asymetric encryption whos output size is quite equal to the input size

For ECC you are probably better off just using ECDSA or, if you're adventurous, the BLS signature scheme. ECDSA has a signature size / overhead of 4x the security strength (say 128 bit), or two times the key size (a 256 bit curve). BLS has a signature size / overhead of about three times the security strength (say 128 bit) or once the key size - it requires a larger key size of 381 bits to reach 128 bit security. So that's about 64 bytes for ECDSA (for a flat encoding without ASN.1 / DER overhead) and 48 bytes for BLS (currently the minimum recommended).

For RSA, see signatures giving (partial) message recovery. For message recovery schemes you will get at least 34 bytes of overhead (assuming SHA-256) - but that doesn't matter much because the minimal signature size is at least the same size as the RSA key size. A rather small key size of 2048 bits will therefore already give you 256 bytes for a signature that contains all the data.

Using a HMAC is only OK if you trust the other systems that get the key to keep the key secure & play fair (and there is of course the issue of establishing the key in the first place).

For many common runtimes / generic cryptography libs I'd only expect to find ECDSA and HMAC implementations.


It is a date that the creator of the signature chose to sign, usually representing the time at which the signature was created, in POSIX time, namely the approximate number of SI seconds that have elapsed on Earth's surface since January 1, 1972 at 00:00 in UTC, plus 63072000, minus the number of those that were labeled as leap seconds in UTC.

The Wikipedia article currently (2018-03-02) names January 1, 1970 at 00:00 in UTC as the reference point, but that must be interpreted as proleptic UTC because modern UTC, or just ‘UTC’ today, did not begin until 1972.  The OpenPGP standard, RFC 4880, §3.5 ‘Time fields’ makes the same mistake, and does not mention leap seconds, but basically all implementations agree to subtract the number of seconds that were labeled as leap seconds.

You can print a UTC representation of the same date and time given its POSIX time representation using the GNU coreutils date(1) utility as follows:

$ date -u --date=@1281838967
Sun Aug 15 02:22:47 UTC 2010


When we encrypt-then-MAC, how do we defend the 2 parts?

When we encrypt-then-MAC (which is the recommended case), do we send both in the same package?

Yes

  Both can be modified along the way, isn't it?

Yes, but not without the MAC check failing.

  how do we defend the 2 parts?

You don't need to do anything else. The MAC is the protection.


How to compute certificates using Diffie-Hellman key exchange with certificates and Elgamal signature scheme

I am currently working through this myself. I believe that the variable $b$ refers to the public key, which you will find using the $\alpha^a \bmod p$ equation you mentioned. Given that, you have all the information you need to find $x$.


One Time Pads and reuse of the decrypted message?

First things first: what you are describing there is not a one-time-pad!

As I explained in another answer of mine:

  Per definition, OTP requires the “key“ to be…

  a truly random one-time pad value,
  generated and exchanged in a secure way,
  at least as long as the message, and
  only to be used once.

What you describe (eg: using a key going Orange Fish) can merely be compared to a simple, keyed substitution cipher with security boundries comparable to a regular Ceasar cipher. Differently worded: your encryption technique is no where near the cryptographic security a real one-time-pad can provide.

Now, to the core of your question: if Bob would base his key on the plaintext of what Alice send him, you would practically be creating a ciphertext by combining two plaintexts (which should actually remain secret).

To attack such a simple “cipher“, an attacker could simply exploit the statistical bias coming from the fact that both the key as well as the ciphertext are regular, human language. Letter frequencies et al would quickly help differring the key from the plaintext. The fact that the space character doesn’t even get encrypted, makes it even easier to recover the plaintexts. The result of using such an “encryption“ would be that an opponent would quickly be able to successfully attack it, and recover both the message Alice tried to secretly send to Bob, as well as the message Bob secretly tried to send to Alice as a reply.

Simpler said: your idea incorporates more than the usual danger of leaking a single secret… because it practically risks the leaking of two secrets: the plaintext which is being send, and the previously received plaintext which is reused abused as key to encrypt the plaintext to be send.

As for an example of the cryptanalytic side of things, I’ll refer you to this question and its accepted answer, as they provide a lengthly and indeep insight on how one could extract a keyword from a keyword cipher – including a practical example. When reading that Q&A, keep in mind that your “algorithm” may seem similar, but actually is much simpler and incorporates more insecurities than what they are talking about there.

Long story short: the fact that Bob and Alice are risking to leak both their secrets twice is pretty inacceptable from a cryptographic point of view. Yet, I am sure every potential attacker will be more than happy when you allow him to gain a complete transcript of your communication in such an simple way; especially since you are including all those nice carbon-copies of the plaintext, which are (ab)used as keys.

Honestly, if I were a cryptanalytic opponent facing your idea in a practical situation, I’ld probably put you on my Christmas-card list for providing me with one of the easiest and most amusing jobs ever.


How should one refer to the smallest remainders generated by a modulus within DH or DLP?

The space $\mathbb Z/n\mathbb Z$ is usually taken to consist of equivalence classes modulo $n$ called residue classes—equivalence classes of integers under the equivalence relation $a \sim b$ if and only if $n$ divides $a - b$.  For example, $\mathbb Z/3\mathbb Z$ consists of the three equivalence classes

\begin{align}
  3\mathbb Z &= \{\dots, -3, 0, 3, 6, \dots\}, \\
  1 + 3\mathbb Z &= \{\dots, -2, 1, 4, 7, \dots\}, \\
  2 + 3\mathbb Z &= \{\dots, -1, 2, 5, 8, \dots\}.
\end{align}

Residue classes are sometimes also called cosets in group theory.

Any set of distinct representatives of all the equivalence classes modulo $n$ is called a complete residue system modulo $n$.  For example, $\{0,1,2\}$ is a complete residue system modulo 3, as is $\{99,-26,-1\}$.

Usually if we want to choose particular representatives for computation, we choose the least nonnegative residues like $\{0,1,2\}$, where each number is taken to represent the equivalence class it is an element of.

There are also more exciting systems like Montgomery residues in radix $r$, where a coset $a + n\mathbb Z$ is represented by the integer $a \cdot r^{-1} \bmod n$, where $r^{-1}$ is an integer such that $r \cdot r^{-1} \equiv 1 \pmod n$.  For instance, in radix 8, modulo 5 we have the representatives

\begin{align}
  0 &\mapsto 0 + 5\mathbb Z, \\
  2 &\mapsto 1 + 5\mathbb Z, \\
  4 &\mapsto 2 + 5\mathbb Z, \\
  1 &\mapsto 3 + 5\mathbb Z, \\
  3 &\mapsto 4 + 5\mathbb Z.
\end{align}

This peculiar-looking function has the property that we can compute a representative of its image by $$\rho(x) = \bigr(x + n\cdot[(x \bmod r) \cdot n' \bmod r]\bigr)/r,$$ where the only divisor involved in the computation is $r$.  Here $n' n \equiv 1 \pmod r$, and the result is either the least nonnegative residue modulo $n$, or the next one greater, so you can get the least nonnegative residue with a single conditional subtraction.  The form $a \cdot r^{-1}$ is preserved by addition and subtraction, $(a \pm b) \cdot r^{-1} = a \cdot r^{-1} \pm b \cdot r^{-1}$, and while it is not preserved by multiplication, it can be restored by evaluating $\rho$: $$(a \cdot b) \cdot r^{-1} = \rho\bigl((a \cdot r^{-1}) \cdot (b \cdot r^{-1})\bigr).$$  This technique is called Montgomery multiplication.  When $r$ is a natural machine word size like $2^{32}$, this representation can be considerably faster without timing side channels than reduction modulo a general odd $n$.


Research topics related to cryptography and Hamiltonian cycles

Cycles (not necessarily Hamiltonian) in the Cayley graph correspond to relations among generators of the group. The RSA assumption can be written as "It is computationally difficult to find a non-trivial relation in the RSA group $(\mathbb{Z}/pq\mathbb{Z})^*$", which is a property of $(\mathbb{Z}/pq\mathbb{Z})^*$ known as being "pseudo-free" (see The RSA Group is Pseudo-Free), so the computational complexity of finding cycles in the cayley graph can be connected to more standard cryptographic assumptions via this notion.

If one wants to force this point of view, you can see the sieving step of index calculus attacks (on both factoring and discrete log) as finding relations in between group generators (this is the standard notion), so finding cycles in the cayley graph of certain groups. While the discrete log problem is defined over a cyclic group (who's cayley graph is simply a $n$-gon), it's not clear to me what particular cayley graph one would be finding cycles in.
In particular, for the discrete log problem you fix a "factor base" of various different generators of the group, and then find relations between their discrete logarithms (with respect to a fixed generator), so the cayley graph does not appear to be just that of a cyclic group (which only has a single generator).

Neither of these deal with Hamiltonian cycles though, and one doesn't need the cycles to be Hamiltonian for the problem to be difficult.