Cracking RSA ciphertext without a public key

It is asked if in RSA, without the public key,

  it is likely much more difficult (if not almost impossible) to find the correct prime numbers, the value $e$, and the value $d$.

As first noted by Tylo in comment, if the RSA key was chosen competently, it will be impossible to find the prime numbers and $d$. Argument: if there was a method making that possible, then that method would also break regular RSA (with the public key available to the attacker); and that's a well-studied and unsolved problem, including if RSA is otherwise used incompetently (like, without padding as in textbook RSA).

Wether it will be possible to find $e$ depends on how $e$ was chosen, on the RSA padding, and on if sufficiently many known plaintext-ciphertext pairs are available:

If $e$ was chosen at random in a large enough set (e.g. as a random odd integer with $2<e<(p-1)(q-1)$ and $\gcd(e,p-1)=1=\gcd(e,q-1)$ ), then it can't be found (argument: that $e$ is also the private exponent in an RSA system with the public exponent $d$, and we just said the adversary can't find the private exponent).
If $e$ is small, it can be guessed (much more if it is among the usual values $e=2^{(2^k)}+1$ with $0\le k\le4$, and $e=37$ ).
If additionally there is no random padding (as in textbook RSA), and a number of known plaintext-ciphertext pairs $(m_i,c_i)$ is known, then a guess of $e$ can be verified, and $N=p\;q$ found, by computing the GCD of enough ${m_i}^e-c_i$ (where the exponentiation is not modular). Because $N$ divides ${m_i}^e-c_i$, for enough plaintext-ciphertext pairs, this GCD will be $1$ for an incorrect guess of $e$, and $N$ for a correct guess.


Is flipping the bit belonging to encryption?

The book "Cryptography Engineering - Design Principles and Practical Applications" was recommended to me on this very site.

From the book:

  Bob needs two things to decrypt the ciphertext. He must know the decryption algorithm D, and the key Ke. An important rule is Kerckhoffs' principle: the security of the encryption scheme must depend only on the security of the key, and not on the security of the algorithm.

While I've only just started reading it myself the mention of Kerckhoffs' Principle (see
Why should I make my cipher public?) is most relevant to your question.

The method you present uses an algorithm but has no key. So anyone who learns how you are flipping bits could restore your original image.

Let's just call your method "image obfuscation".


Is it possible to calculate the 'skeleton key' for DUAL_EC_DRBG? What would it take?

I've found this attack to be poorly documented, all-in-all. Below is a technical explanation of the matter, or one can skip to the conclusion if uninterested in the details.

Dual_EC_DRBG

First, let me give a short description of Dual_EC_DRBG using the notation of Shumow and Ferguson (see the presentation). As a preliminary, we are working with some prime-order elliptic curve, and we have two points $P$ and $Q$ on that curve. Since the group is prime-order, both $P$ and $Q$ are generators.

Since we'll be working with integers ultimately, we need a way to "convert" a point on the curve into an integer. For that purpose, we will define $\varphi(x, y) = x$, i.e., we just use the $x$-coordinate of the point.

In any round $i$, we have a starting state $s_i$. Next, we compute $$r_i = \varphi(s_i P)$$ where $s_i P$ denotes repeated point addition:
$$s_i P = \underbrace{ P + P + \dots + P.}_{s_i \text{ times}}$$
This $r_i$ will be used to (1) generate the output and (2) update the state of the generator.

The output of round $i$ is
$$t_i = \operatorname{LSB}_{\mathrm{bitlen}-16}(\varphi(r_i Q)).$$
The attacker will be working with these values. Here, $\operatorname{LSB}$ means "least significant bits," so we chop off 16 bits before we output.

The state of the next round is defined by $$s_{i+1} = \varphi(r_i P).$$

The Attack

Since $P$ is a generator, there is some integer $e$ such that $P = eQ$. Suppose we know this $e$.

Given any output $t_i$, we know all but sixteen bits of the value $\varphi(r_i Q)$. We can generate all possible combinations of those missing sixteen bits, which leaves us with $2^{16} = 65536$ possible values — one of which is $\varphi(r_i Q)$, the "real" output. Since all $(x,y)$ points on an elliptic curve satisfy the equation $y^2 = x^3 + ax + b$, if we are given some $x$-coordinate, we can solve the quadratic to obtain two possible $y$ values. That is, if we have $2^{16}$ values that might be $\varphi(r_i Q)$, we can use each of those values in the previous equation, and thus obtain $2 \cdot 2^{16} = 2^{17}$ values, one of which is the real $r_i Q$.

What happens if we have $r_i Q$? Since we're assuming we know the $e$ such that $P = eQ$, we can simply multiply $r_i Q$ by $e$ to get:
$$e(r_i Q) = r_i (e Q) = r_i P.$$
Recall that the state of the next round is defined to be
$$s_{i+1} = \varphi(r_i P).$$
So if you know the $e$ such that $P = eQ$, you can predict all future states of the generator, which means you can predict all future outputs of the generator.

How do we determine which of the $2^{17}$ values is $r_i Q$? Simple: we try to predict the next round's output, using the above attack, for multiple rounds. When one value fails to predict the next state, it is obviously not the real $r_i Q$, and so it can be thrown out. This process eliminates all but the real $r_i Q$. Shumow and Ferguson found that approximately 32 bytes of output was sufficient for this attack to succeed.

Conclusion

Your question:

  Is it possible to calculate these secret numbers given these constants? What would it take to calculate them?

It is possible, but not feasible.

The secret integer $e$ (where $P = eQ$) is the necessary value to find. Computing this $e$ from scratch (with arbitrary $P,Q$) requires solving an instance of the discrete logarithm problem in the elliptic curve: $e = \log_Q P$. At present, it is considered computationally infeasible to compute the discrete log in this case.

However, if you are the one picking the point $Q$, you can select a random integer $d$ (to use Shumow and Ferguson's notation again) and set $Q = d P$. Then $e = d^{-1}$, which is quite easy to compute.

Thus: unless you are the one who picked the point $Q$, you have basically no hope of finding $e$. On the other hand, if you did pick $Q$, then you could have very easily picked $Q$ such that you know $e$. This is pretty much the textbook definition of a backdoor, I think.

Note that two problems in tandem cause this attack: first, if we had picked a better way of integer-izing an elliptic curve point (a better $\varphi$), it wouldn't be possible to use $\varphi(r_i Q)$ to find $r_i Q$. Second, since we only chopped off sixteen bits before output, it is easy to brute-force test all missing sixteen bits. If we had chopped off more bits, the attack would maybe have been thwarted.


Possible data leak when duplicating encryption?

Any good encryption algorithm is resistant to known-plaintext attacks, i.e. an adversary who knows the encryption of certain plaintexts has no advantage in finding the key or even in encrypting other plaintexts or decrypting other ciphertexts. This means, in particular, that the adversary can't find the key. Good encryption algorithms even have stronger properties — even if the adversary can choose the ciphertexts or the plaintexts, they can't reconstruct the key, or encrypt/decrypt other plaintexts/ciphertexts. (That latter property only works for authenticated encryption — with non-authenticated encryption, there are systemic chosen-ciphertext attacks, such as decrypting a prefix of a ciphertext whose decryption is known.)

Barring implementation bugs, having access to the plaintext via one of the keys is of absolutely no help to find the other keys.


Construct block cipher from a smaller one with mixing function

I read about the AEZ encryption scheme as presented at the CAESAR competition. To me it seems like a construction of an arbitrary length block cipher from a smaller one.

The construction is only used in the v1.x of AEZ, because it requires appriximately 1.8 AES calls per block of plaintext, while the one used in v2.0 requires only 1 AES per block asymptotically. It is originally due to Naor and Reingold.

It is more like a block cipher mode than a way to construct a larger block size cipher from a smaller one. Specifically, it does not improve the birthday bound which limits the number of blocks encrypted to less than the square root of block size (i.e. $2^{64}$ for AES).

  In my opinion the properties of a mixing function would be:

The requirements for the mixing function are given in the paper above. It is enough that the functions MIX and MIXI are pairwise independent permutations, but that is not a strict requirement. Instead it is enough that they are $\epsilon$-AXU2: $\forall x \not = y, z \in \{0,1\}^n: P[f(x) \oplus f(y) = z] \le \epsilon$.

The paper NR mode of operation (ps) refers to several types of functions that fit the bill if you are interested in using something else.


Diffie Hellman Exponentiation Implementation Problem

There is a well known technique for exponentation, you might read this http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method . The same techniques and its variants are used for matrix exponentiation ... You only need 256 squaring and at most 256 multiplications.


Is the inverse of a point on an elliptic curve over $\mathbb{Z}_p$ always in the group?

poncho has it right, I was calculating the inverse incorrectly. The inverse of a point $(x,y)$ is $(x, -y)$. It just so happens that $(x,y) + (x, y^{-1}) = 0$, but this was a red herring. Thanks!


DH key exchange with only one end authenticated

…what if I only verify the signature of one end?

Bob would not be able to know if he is looking at a signature by Eve, or if it’s a valid signature coming from Alice. In case if Eve is messing with the exchange, Eve would be able to inject her own (as it is handled non-authenticated) and Eve would be able to verify that it’s Bob on the other end (which boils down to “non-deniability”).
Depending on the individual situation, these can be a real neck-breakers.

  Is there any vulnerability then?

Yes! As described above, there is a vulnerability in that case because one authenticated party would be “talking” to an non-authenticated other party… whoever that may be. That’s why authentication is regarded to be so important in the realms of cryptography – to detect if Eve is messing with things.


Comparison Affine Coordinates and Projective Coordinates Addition in Excel

The projection coordinates you got are wrong. We can tell that because those coordinates do not correspond to a point on the curve.

We have $15 \cdot 9^{-1} \equiv 17$ and $2 \cdot 9^{-1} \equiv 13$; when we plug $x = 17$ and $y = 13$ into the original curve equation, we do not get equality, and so we know something went wrong.


How to deal with different setup in Multikey FHE?

This question is related with your other question, and the reason the parties can't use different values of $q$ is the same: operations will not be well defined.

Moreover, the statements, proofs, etc, on the paper you have cited are done assuming that all the users are using the same parameters, which means, not only the same value of $q$, but also the same $B$-bounded distribution $\chi$, the same cyclotomic polynomial $\phi$ and so on...

For instance, take a look at lemma 3.6. The authors start it by fixing the parameters and then saying that the scheme is "multikey homomorphic for $N$ keys".

So, the users have to agree about a set a parameters and then generate their own keys independently.


If you know the Fermat's little theorem, that is, $g^{n-1} = 1 \mod n$, then you can understand what you found.

The point is that

$$b^2 = g^{2k + n-1} = g^{2k}g^{n-1} = g^{2k} = a^2 \mod n$$

Therefore, $b = a$ or $b = -a$ in $\mathbb{Z}_n$. But $b = -a$ means that $b = n-a$, since $n = 0$ modulo $n$.


Message Expansion / Encryption Blowup Factor / Ciphertext Expansion of ECC

OK, a short amendment to your table, "message-expansion" only applies to messages which are quite long and not trivial one-bit messages, because they'd have a much higher message expansion.

Secondly, RSA doesn't have an expansion of "1" because of constructions such as OAEP. Also note that plain RSA has no form of semantic security and only improved variants provide IND-CPA and IND-CCA2 security.

Thirdly, McEliece can do better than "2" and usually does, depending on the details, it should have something around 1.5 at worst, also see Bernstein's Post Quantum Cryptography book and this paper (PDF). Depending on whether you want IND-CPA or IND-CCA2 security, better results may be achieved.

And now finally for ECC using ElGamal. Note first that you can't encode arbitrary messages deterministically as elliptic curve points and thus you can't easily encrypt arbitrary messages using this method.
The rest can be seen from the description in which is stated that the output effectively is two group elements and as two group elements usually are twice as large as a single group element (the message), you get a message expansion of "2". Note also that plain ElGamal is only IND-CPA and not IND-CCA2 secure.


Help understanding how to decrypt cipher

You don't start by manipulating the last byte of the first block. Rather you manipulate the last byte of the last block. You start at the end and work backwards. The side-channel leak in the padding oracle attack is that the server distinguishes between a bad cipher and bad padding. This is the leak that lets you figure out the message.

If you try every possibility for the last byte, the server will tell you if the padding is bad. If you get no "bad padding" error you know the value you tried is likely 1 xor'd with what will decrypt the last byte of the actual message. So then you try changing the last two values to get "2" and "2". You already know to xor 2 with the last value at the end that gave no bad padding error. So it's a matter of figuring out the second to last byte and trying every byte until you get no padding error and so on.

The best way to understand this that I know of is to do the cryptopals challenge (google it). It's also very helpful to look at a diagram of how CBC works because you can visualize what's happening.


Calculate if a digital signature is valid

Basically RSA signatures work just like encryption but with the keys exchanged.
If somebody tells you $m^{sk}$ you can easily test if
$$
(m^{sk})^{pk} \equiv m\ (mod\ N)
$$
but you cannot calculate $m^{sk}$ yourself.

The problem/trick is the usual, exponentiation is easy but logarithm is hard.

(I like using $sk$/$pk$ for secret-/public-key rather than $d$/$e$ for decryption-/encryption-key as it makes more sense for signatures.)


Quite a few message authentication codes are actually PRFs with arbitrary input domains.  For example:

HMAC, instantiated with a hash function satisfying the appropriate security properties (basically, for Merkle–Damgård hash functions like the SHA-2 family, that the internal compression function is itself a PRF), is provably a PRF.
CMAC, instantiated with a secure block cipher (i.e. a PRP), is provably a PRF.

In both cases, the security proofs are conditional on certain assumptions about the underlying primitives (hash function / block cipher) that cannot themselves be proven (at least not for any practical crypto primitives currently in use) without further assumptions.  Thus, the best we can do is choose a standard and well studied hash or cipher, like SHA-2 or AES, and hope that the fact that they've been studied by many skilled cryptanalysts, without any published successful attacks, is proof enough that they cannot be broken with current state of the art.

In general, these PRFs take an arbitrary string as an input, but produce a fixed-length bitstring as their output.  If a longer output is desired, one simple way to extend it is to re-run the PRF on the same input, but with a different (ideally, independent) key.  (There are other, potentially more efficient ways to extend the output length, but they require more involved security proofs; see e.g. Maurer & Sjödin (2007).)

As for the key length, this depends on the scheme in question; for example, the CMAC key size depends on the block cipher used, while HMAC technically accepts keys of any length, but keys longer than one hash input block are processed by hashing them first (which implies that the effective maximum key size, measured as resistance to brute force attacks, is limited by the hash block size).

Thus, the arbitrary key length of HMAC should be regarded as a convenience; it does not imply arbitrarily high cryptographic strength, but it does mean that, if you happen to have a long but low-entropy key, like a user-entered passphrase, you can feed it to HMAC without having to reduce it to a fixed length first.  This is a convenient feature for key-derivation functions, many of which are based on (or commonly instantiated with) HMAC.

(As for increasing the key length in the hopes of increasing cryptographic strength, it's worth noting that a brute-force attack on a 256-bit key is far beyond any existing or conceivable computational power, even if quantum computing turns out to be practical.  Thus, for all practical purposes, 256 key bits is more than long enough.  Also, if you still, for some reason, want higher brute force attack resistance, you'll need to pay close attention to the actual security bounds claimed for the primitives you're using, and the tightness of the security proofs, since even attacks usually seen as being only of theoretical relevance may become practical for hypothetical attackers wielding such implausibly high levels of computing power.)


Information theoretic message authentication code (MAC)

Just collecting some of the comments, if you make sure that $a$ and $b$ are chosen uniformly at random with $a \neq 0 \mod p$, then the given function is a information-theoretic MAC, basically because it satisfies the following property:

  If $h_k(m) = am + b$ with $k= (a,b)$ and $\tau$ is the codomain of $h_k$, then for all $m\neq m'$ and $t,t'\in\tau$ we have
  $$\operatorname{Pr}[h_k(m) = t \ \wedge\ h_k(m') = t'] = \frac{1}{|\tau|^2}$$
  (probability taken over random choice of $k$)

When a function satisfy this property we say it is a strongly universal function, and the main result is that such a function is a $1/|\tau| -$secure MAC, that is, the advantage of an attacker is at most $1/|\tau|$ (notice we can not ask for this advantage to be zero because any adversary can always try to guess a valid tag).


Is there a quick method of listing certain elements of a cyclic group?

Since this is a field, you know that the polynomial $x^2-2=0$ may have up to 2 roots, no more. You could use the quadratic formula (since the polynomial ring over a field is an integral domain) but this would require the extraction of a square root. But it is certainly more efficient than checking all elements.

Also if if $a$ in $x^2-a$ is a square then you can factor $(x^2-a)=(x-b)(x+b)$ where $b^2=a.$


About ORAM initalization and running out of space

Are there any scheme to increase ORAM storage with time while maintaining oblivious?

I found this paper that addresses the issue of obliviously resizing:

Moataz, Tarik, Travis Mayberry, Erik-Oliver Blass, and Agnes Hui Chan. "Resizable tree-based oblivious RAM." In Financial Cryptography and Data Security, pp. 147-167. Springer Berlin Heidelberg, 2015.

I also recall a talk by Elaine Shi where she discussed resizable ORAM, but I can't find the relevant paper.


ECDH or RSA more secure for symmetric key wrapping?

Yes, there are a few reasons to prefer ECDH over RSA:

ECDH will perform much better;
ECDH can provide forward security when used with ephemeral key pairs without a large performance overhead for creating those key pairs;
ECDH should be impervious to most oracle attacks, i.e. timing based padding oracle attacks on OAEP.

For the forward secrecy you require two ephemeral key pairs (to perform ephemeral-ephemeral Diffie-Hellman). Ephemeral key pairs cannot be used for authentication, so you require additional steps if you wanted to use a static ECDH key pair for this.

There are a few drawbacks as well:

RSA is generally much better understood;
there is some discussion about EC security and domain parameters: you may need to validate the public key point or use one of the Safe Curves.

Although you may have to perform more modular calculations - including modular exponentiation - for ECDH, the modular calculations are over much smaller numbers, leading to a much better performing algorithm, especially regarding calculations that use the private key.

Textbook or raw RSA is perfectly able to handle big secret keys; any normal sized secret key can be directly encrypted with a normal sized RSA public key. It's just required to interpret the padded secret key as a number. RSA padding schemes such as OAEP are required to obtain security.


Understanding a faulty Needam-Schroeder protocol

The trick here is that Trudy does not need to know $K_{bc}$ (as you mentioned, it's not public).

However, what Trudy really needs to do is observe (by just monitoring the network) and store a previous "$K_{bc}(K,A)$" value that A has sent to B (publicly) beforehand (step 4).

So now in any future protocol sessions. Given that $K_{bc}$ is going to be the same, Trudy has the previous value it needs to preform the replay attack.


Strategies to address an immutable key in a symmetric cryptosystem

I'm not sure if this is precisely what you are asking, but developing single-session keys from a long term hard-wired key is something that mobile phones and SIM cards do. Hard-wired keys on the SIM and known to the service provider kick off key derivation process augmented with a random nonce value from the service provider's base station. The 3GPP MILENAGE suite is such a method, is standardised via ETSI, and only uses symmetric primitives (block ciphers).


Is the DES F-function injective for a given subkey?

Yes, it can; within the DES round function, two different 'right side' inputs can, after the sboxes, come up with the same value to xor into the 'left side'.

This was a deliberate decision by the DES designers, who thought that this was an important property.  I don't know their reasoning about why they thought it was important.


Homomorphic encryption or double symmetric encryption?

As CodesInChaos mentioned in the comments: If you have a trusted party, you don't need homomorphic encryption.

More to the point of the question-- No.

A "reasonably optimized" (especially, like NTRU, fully) homomorphic encryption scheme should always be somewhat slower / less efficient than using plain symmetric-key encryption (and 'plaintext operations' outside of a ciphertext).

To see this is not just true, but should ALWAYS be true: Note that any FHE scheme is also a symmetric-key encryption scheme (ignore the homomorphism; let the scheme's public-key be kept secret as a private encryption key). Extra features can't come for free. The best you can hope for is 'not much overhead in practice,' but (F)HE will never be faster in general.

Bonus thought: Short, and hopefully more intuitive, "proof" that FHE.Eval is /always/ going to be more expensive than the SYM-1.Dec + basic operations + SYM-2.Enc option--

Note that the decryption operation in EVERY KNOWN fully homomorphic encryption scheme is close-to-linear time: With lattice cryptosystems, you're always performing inner product of a ciphertext-vector $c$ with a key-vector $s$ (then rounding) in order to decrypt. No matter how much computation you do, the encrypt/decrypt cost remains the same.

Further, assume each 'plaintext operation' of cost "C" has cost at least "C+1" when you perform it homomorphically. ("Only +1" is quite generous.) Since FHE should allow unbounded computation, just consider computing FHE.Eval longer and longer until the "C+1"-per-operation overhead offsets the small, one-time cost of encrypting/decrypting.


Storing a secure key in an embedded device's memory

An issue with storing a key in RAM is, there are attacks that involve erasing the flash to unlock the device and then using a debugger to copy the RAM contents. Problem with internal EEPROM is the same as RAM unless you can lock it. External EEPROM is worse, unless you encrypt that.

My druthers would be store the key in flash and then lock the lock the processor to disable debugging access. If possible use a separate key for each and every device. If you copy the key to ram, make sure it's gets over-written when done.


To answer your original question: no, you can't presume that you can replace the addition mod $2^{128}$ within $Poly1305$ with XOR, and not change the security properties (at least, not without some serious analysis).

The security of the MAC depends on the fact that, given any two distinct messages $M_1$ and $M_2$, and any integer $\Delta$, then the following is true only for a limited number of values of $r$:

$H_r(M_1) - H_r(M_2) \equiv \Delta\bmod 2^{128} $

In other words, if you treat this as an equation in one unknown $r$, then there is only a small set of solutions, no matter that $M_1$, $M_2$ and $\Delta$ are (assuming $M_1 \neq M_2$)

If you replace the addition in $Poly1305$ with exclusive or, then the corresponding relationship would be:

$H_r(M_1) \oplus H_r(M_2) = \Delta $

It may be the case that one might be able to find clever values of $M_1$, $M_2$ and $\Delta$ where this holds for a number of values of $r$; if this is possible, then this would cut severely into the security properties.

Now, it is possible that this altered equation also has a bounded number of solutions in $r$; unless someone does some analysis and shows that, it seems unwise to trust it.


Security of CCM in TLS, in comparison to GCM, SHA or SHA2 for the digest

GCM and CCM are both basically fine as far as typical TLS use goes, although there is a litany of caveats for them:

Anything involving AES is likely to be vulnerable to timing side channel attacks, if you cannot guarantee that you are using hardware implementations of AES.  (Portable C code cannot.)
GCM is also likely to be vulnerable to different timing side channel attacks, if you cannot guarantee that you are using hardware Galois field arithmetic.  (Portable C code cannot.)
The length of the authentication tag directly affects security: the GCM and CCM suites use 128-bit tags, but the CCM-8 suites use 64-bit tags, so they cannot get better than a 64-bit security level against forgery.
For both GCM and CCM, the security contract requires that the key never be reused with a nonce.  If they were integrated into TLS sensibly, the protocol would mandate the use of sequential nonces, so that there is only one possible choice of nonce for each message and if a peer chooses any other nonce it will noisily fail to interoperate.  TLS 1.3 will do this, but when GCM was first introduced for TLS, it was foolishly designed to allow the peers to choose nonces however they like, to hilarious effect, and CCM in TLS parroted the mistake.

You can't fix any of these problems except by picking an entirely different cipher suite, but you can check whether these are problems for mbedTLS or your particular deployment of it—make sure mbedTLS uses sequential nonces, for example, and take a close look at how it computes AES and GHASH.

Or, if mbedTLS and your clients support it, just always use ChaCha20/Poly1305 cipher suites instead, which have none of these issues.


No.

The short authentication tag makes for high probability of forgery.  But that's not relevant here.

The short nonce limits the number of messages that can safely be encrypted with the same key—indeed, narrowing it down to two possibilities limits it to two messages.  But you have only one message.

What's left is breaking AES.  Good luck!


Why does RSA 1024 provide lower security level than EC256?

There are some more efficient algorithms (still super-polynomial time, not enough to actually break them) to solve discrete logarithm problems and integer factorization problems, hence keys based on these problems are longer than EC based cryptographic keys which provide equivalent security, in which no such algorithms significantly better than birthday attack are known.


Birthday-paradox for big numbers and more than one person: Computing the approximate probability of $k$ hash collisions for $n$ hashes

For large $k$ growing with $n$ the binomial coefficient needs to be approximated.

Let $h(x)=-x\ln x-(1-x)\ln (1-x)$ be the binary entropy function in nats, then for $k\in [1,n-1]\cap \mathbb{Z}$ we have
$$
\sqrt{\frac{n}{8k(n-k)}}\exp\{nh(k/n)\} \leq \binom{n}{k} \leq \sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\}
$$
where the upper bound approaches equality if $k$ and $n-k$ are both large. This is obtained from Stirling and then some other manipulation, and covers the whole range of $k$.

This result appears, e.g., in Bob Gallager's book Information Theory and Reliable Communications.

This will give a good approximation if you use the upper bound.

So, you have
$$
1-\exp\left[-\frac{\sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\}}{\exp\{(k-1)\ln 2^{32}\}}\right]
$$
and can further take differences of the exponential function arguments inside and simplify for $n=2^{64},k=2^{32},$ to
$$
1-\exp\left[-\sqrt{\frac{n}{2\pi k(n-k)}}\exp\left(nh(k/n)-(k-1)\ln 2^{32}\right)\right]\approx$$
$$\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left(nh(1/k)-(k-1)\ln 2^{32}\right)\right]
$$
or
$$\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left(nh(2^{-32})-2^{32}\ln 2^{32}\right)\right]
$$
and since for large $k$, $h(1/k)\approx \ln k,$
$$\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left(n \ln 2^{32})-2^{32}\ln 2^{32}\right)\right]
$$
$$
\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left((2^{64}-2^{32}) \ln 2^{32}\right)\right]\approx
$$
$$
\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left(2^{64} \times 32 \ln 2 \right)\right]
$$


Counter Mode in Advanced Encryption Standard(AES) Algorithm

Yes, that's correct assuming you have, say:

0x347ABCD98....000000001
       |             |
       |             --- Counter (64-bit width)
       |
       ----------------- 64-bit nonce prefix

What you're trying to do is ensure that each 128-bit AES block is xor'd with a different value.

The reason for this is that, if you take typical AES, you have a key schedule which expands your key size to a longer stream that appears random. However, should your data repeat and the values of the key schedule repeat, you'll effectively begin to see patterns.

Using a unique counter essentially attempts to ensure that no plaintext blocks ever repeat for the same key - taking any two plaintext blocks and xoring them with an ever increasing value guarantees that. The block cipher primitive guarantees your secrecy, so the result should be a stronger than ECB cipher.

There are two obvious caveats to what I've just said, however:

Each IV must be unique per key. If it isn't, then you run the chance of generating patterns over a sufficiently large collection of ciphertexts. See this answer.
Each nonce (generated from the IV + counter) must be unique.

With a 64-bit split in the field, you effectively give yourself $2^{64}$ possible uses of a key and a maximum stream length of $2^{64}$ 128-bit (that's $2^{64}*16$ bytes) blocks - which when you work this out should be more than enough storage space and key uses

The split I'm talking about here is actually in general hypothetical. If you're only ever using the key once, you could use the entire space.


Which cipher mode should I use, taking into account packet loss? I was thinking about CTR since it does not depend of previous/next packet to encrypt/decrypt each packet.

That doesn't matter too much. However, if you go for CTR mode you must make sure to never repeat the IV. Using a counter as nonce/IV is not such a good idea if there is package loss. You should probably have some way of ordering packets anyway, so you could put a sequence number in each generated packet and use that.

Note that you should not use the same key for two way communication. Also note that CTR mode doesn't protect against alteration of the data (so an attacker could at the very least insert noise). Timing and data rate may also tell an attacker a lot. With audio / voice there are a lot of ways to leak data through side channel attacks.

  Is it safe to NOT use an IV in this case (always use zero or NULL)?

Not with CTR mode if you value the confidentiality of your plaintext. When reusing a key you should generally always use different IV's. For CBC mode they should even not be predictable by an attacker.

As the data contains audio (which isn't that structured) you could possibly take some leeway with some of the constraints, but history tells us that this is very dangerous indeed. Besides that, it's often the case that packets also contain important meta-data, if just to control the network connection / stream.

  As far as I got my code done, I had to initialize a new EVP context for each audio packet, so that there wouldn't be any bytes left to be written to the encrypted datagram. If I don't do this, my audio packets may be currupted. Is this the right way to overcome this issue?

Already answered here.


How feasible would it be to generate 300 million public key pairs in 8 hours?

It is feasible to generate 300 million public key pairs of reasonable strength in 8 hours on a single computer, easily with ECDSA using a single core/thread, and even with DSA using quite a common multi-core computer.

RSA would require many standard computers (baring hardware accelerators for modular exponentiation), assuming all the public keys are made public (see Poncho's answer otherwise, applicable for example if you wanted to generate a single PGP RSA key pair of reasonable security and having the same 32-bit key id as one in 6 pre-existing PGP keys, which is likely achieved with 800 million randomly generated keys).

Generating an ECDSA keys pair is as simple a generating a random private key (of e.g. 256 bits for the common P-256 parameters), and doing one point multiplication. These benchmarks show ecdonaldp256 key generation requires about 300 thousands cycles on a single core and thread of a 3.5GHz CPU, giving more than 10 thousands keys per second, over twice the requirement. And then ed25519 is more than 4 times faster.

Entropy is not an issue, we can even use manual dice throws to seed a CSPRNG, and discard the seed. Also, many modern CPUs have built-in hardware RNG with high throughput, and we can use this if we frown at having all the keys depending on the same seed (but then we still have all the keys depending on the integrity of the same computer, and what's connected to it, which is more of a security concern IMHO).

We can use several cores in parallel, and/or several computers (we can use the same seed on each job, just use the job number as an extension of the seed).

DSA key generation is significantly slower for comparable security, mostly because we need 2048-bit modulus, when P-256 works with 256-bit modulus (and only a few times more such operations). The same benchmarks show donald2048 about 4 times slower than ecdonaldp256 for key generation, and reaching the performance goal with a single computer will require some level of parallelization, but we still reach about twice the stated goal with all 4 cores of some of the CPUs benchmarked. And then high-end single-board servers may have 8 CPUs each with 18 cores.

RSA key generation is much slower for comparable security. The same benchmarks show ronald2048 as more than 1000 times slower than ecdonaldp256 for key generation. That's mostly because RSA key generation requires generating random primes, thus trial and error. Effort is dominated by failed primality tests, and attempts to reduce these. If we pre-select for testing integers not divisible by any of the 54 primes less than 256, that is about $1/10$ of integers, we still need to test about $1024\log(2)/10\approx71$ integers to find a 1024-bit prime. That 1024-bit prime generation algorithm will be dominated by about 75 executions of $x\gets a^d\bmod n$ steps in Miller-Rabin tests, each costing a 1024-bit exponentiation to nearly 1024-bit exponent; so key generation will be in the order of 75 times as costly as the exponentiations dominating an RSA signature using CRT.


Can one extend the nonce of ChaCha/Salsa20 by XORing the extra bits with the key?

Maybe. But your scheme hasn't been vetted by the community for its impact.

Better to use XSalsa20 or the related XChaCha20 as recommended by Bernstein himself: http://cr.yp.to/snuffle/xsalsa-20110204.pdf

In my opinion it was a fairly major faux pas that DJB originally chose short 64-bit nonces for Salsa20 and ChaCha20, especially given all the nonce-misuse attacks in the past. Storing a no-chance-to-repeat counter is actually really hard in practice. He then went on to make a "idiot-proof" crypto library that requires a user-supplied nonce for every "simple" box function, and yet doesn't include the nonce in the authenticated cipher text output.


How would you explain this very simple add/modulo asymetric encryption?

If you were to plot the numbers 0-M on a straight horizontal line in increasing order from left to right, your message would become a point on that line. When you apply the key, it moves the message over $a$ spaces to the right. The modulo operator means that if your message goes too far off the right side of the line, then it wraps back around to the left side of the line.

If you were to apply the key $a$ again, your ciphertext message would move over another $a$ spaces to the right, which, assuming an appropriate modulus, implies that the result will not line up with the original plaintext message.

With this in mind, if you were move the ciphertext message instead $b$ spaces forward, you would end up back at the original message.

If you wanted to use $a$ as a symmetric key, you would instead perform modular subtraction on the ciphertext using $a$. Basically, symmetric decryption "reverses" the transformation, while in the case of asymmetric encryption, the  ciphertext is decrypted by going forward, as opposed to going backwards. This is what enables us to build public key encryption from non-invertible functions - we do not invert the transformation, we design it such that "going forward" (in a particular way) happens to "line up" and result in the original message.

Other operations can be used to create this asymmetric effect, usually employing a modulus. As mentioned by @poncho in the comments, multiplication is often used as a way to demonstrate "asymmetric crypto", but it should be noted neither addition nor multiplication is "strong enough", typically: modular exponentiation is what is used in practice to achieve the effect.

Here are some simple diagrams using your example. We'll start with a number line:

-----0-----1-----2-----3-----4-----5-----6-----7-----8-----9-----10-----

Setting $a$ at 3:

-----0-----1-----2-----a-----4-----5-----6-----7-----8-----9-----10-----

After we add $x$ (which is 4) to $a$ (which is 3); Since $a$ has been encrypted, we shall refer to the ciphertext as $b$ (as you did), which now has the value of $7$; The addition moves the value to the right on the number line:

                                   +x
                       +-----------------------+
                       |                       v
-----0-----1-----2-----a-----4-----5-----6-----b-----8-----9-----10-----

If we were to add $x$ to our ciphertext again, we would end up at $1$ ($11 \bmod 10 = 1$)

                                                           +x
... -------+                                   +------------------ ...
           v                                   |
-----0-----1-----2-----3-----4-----5-----6-----b-----8-----9-----10-----

This obviously leads to incorrect decryption. To decrypt correctly, we can add the corresponding private key $y=6$ ($x + y = 10$) to make the ciphertext "go forward" to the correct plaintext, remembering to wrap around when we get to the end of the number line:

                                                         +y
... -------------------+                       +------------------ ...
                       v                       |
-----0-----1-----2-----3-----4-----5-----6-----b-----8-----9-----10-----

Remark: here $10$ and $0$ are the same number (because $\mod 10$) !


Key iteration count while using random keyfile larger than master key

Key stretching is only used to make small-entropy keys less vulnerable to brute force attacks. If it is (nearly) impossible to break the original key, than there's little sense in using a iteration count of more than 1.

If the input to the function is as big (in sense of entropy in bit) as the output, then an attacker could just attack the algorithm which did use the output and not the key derivation function itself.


I think what you are asking for here is the so-called notion of black box obfuscation where the behavior of the obfuscated code and a literal blackbox oracle can't be distinguished.

Sadly this has been proven impossible in "On the (Im)possibility of Obfuscating Programs" by Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang with a nice blog post by Green also touching and more informally explaining the topic.

To be more precise about "this" being used above: "this" means here the existence of a general "compiler" taking any program and returning a black-box obfuscated version. Special programs, e.g. functions which only evaluate to true at exactly one point or conjunctions (PDF; thanks Weiken Chen) can be black-box obfuscated.

What is possible though is so-called indistinguishability obfuscation (iO) which allows you to take two programs implementing the same functionality and run them through an obfuscator and now nobody can efficiently tell with which obfuscation they are presented.


RSA: deduce the public key from message & signed message

With only one (message, signature) pair $(M,S)$, it is not known how to recover the public key $(N,e)$. However, that can be done

with two distinct pairs $(M_0,S_0)$ and $(M_1,S_1)$,
and assuming a known deterministic RSA signature padding scheme with appendix, including textbook RSA, hash-then-textbook-RSA, RSASSA-PKCS1-V1_5 (which is believed safe), and a few others (but not standard RSASSA-PSS).

In a deterministic RSA signature padding schemes, the signature of message $M$ is computed by transforming it into a padded message representative $\widetilde M$, then computing the signature $S={\widetilde M}^d\bmod N$. The signature verification step verifying alleged $M'$ against $S$ computes $\widetilde{M'}$ and checks $S^e\bmod N=M'$. Computation of the padded message representative typically involves hashing. Textbook RSA has $\widetilde M=M$, while hash-then-textbook-RSA has $\widetilde M=H(M)$ for some hash function (the fist is unsafe, and the second is only safe for very wide hash).

The attack needs to guess $e$, but that's typically a small integer, often $e=F_i=2^{(2^i)}+1$ with $0\le i\le4$, or $e=37$, with $e=F_4=65537$ common in practice. We need to pad the two messages $M_i$ into their message representatives per the padding algorithm used by the signature scheme, giving $\widetilde{M_i}$ (for RSASSA-PKCS1-V1_5, we need the size of $N$ in octets, which is the same as that of the $S_i$ if expressed as fixed-size octet strings, or typically given by the highest $S_i$ otherwise).

We are now trying to solve a system of two equations with only unknown $N$: $S_i^e\bmod N=\widetilde{M_i}$. In each, if we got $e$ right, $N$ is a divisor of $(S_i^e-\widetilde{M_i})$.

$N$ can often be found by computing the Greatest Common Divisor of the two $(S_i^e-\widetilde{M_i})$. In most of the remaining cases, pulling out a few small factors from this GCD by trial division of small primes will reveal $N$. For random parameters, this almost always works. The only implementation difficulty stems from the size of $S_i^e$, especially for $e=F_4=65537$ (Java's BigInteger gets impractically slow; GMP shines). Much larger $e$ would make the attack difficult.

If we make a wrong guess of $e$, the method fails (typically yielding a much too small GCD), we can detect that and try another $e$.

Note: at least for textbook RSA, it is possible to intentionally pick messages making pulling out small factors difficult. In that case, Pollard's rho or ECM (as in GMP-ECM) could come to the rescue.

Note: I have included a small demo in Java as invisible text at the end of the source of the present answer.


How to generate a 16 X 8 perfectly nonlinear S-box

$A:\mathbb{F}_2^m\rightarrow \mathbb{F}_2^m$ is the state space map induced by the primitive length $m$ LFSR.

Thus it maps the zero vector of length $m$ to itself and in general the LFSR state $(a_0,a_1, \ldots,a_{m-1})$ to $(a_1,\ldots,a_m)$.
$A^i$ is just $A$ iterated $i$ times (shift LFSR $i$ times).

Then, the APN map $z=(z_1,\ldots,z_n)=F(x_1,x_2)$ where $x_1,x_2,z,\in \mathbb{F}_2^m$ is given by
$$
z_i=A^{i-1}(x_1)\cdot x_2,\quad i=1,\ldots,m
$$
where $z_i$ are individual bits.


1 - Is it mathematically possible to generate a shared secret starting with 0x0n using ECDH? (My guess is "yes")

Yes; the shared secret is the $x$ coordinate; approximately half of the values between 0 and $p-1$ (where $p$ is the prime that the elliptic curve is defined over) are possible; there's no reason to believe that the values with a top nybble of 0 are all impossible.

  2 - Is there any rule or convention stating that a shared secret should be shifted so that the first nibble shall never be 0?

I've never heard of one.


Linear Approximation Table of S-Box for SPN

In Howard Heys' tutorial, the S-box $S$ maps 4 bits to 4 bits. It is defined by the following lookup table:

x    | 0 1 2 3 4 5 6 7 8 9 a b c d e f
S(x) | e 4 d 1 2 f b 8 3 a 6 c 5 9 0 7

This can be split in 4 Boolean component functions, by considering the output bits separately. Here, the subscript 1 refers to the least significant bit:

x      | 0 1 2 3 4 5 6 7 8 9 a b c d e f
S(x)   | e 4 d 1 2 f b 8 3 a 6 c 5 9 0 7
S_1(x) | 0 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1
S_2(x) | 1 0 0 0 1 1 1 0 1 1 1 0 0 0 0 1
S_3(x) | 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 1
S_4(x) | 1 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0

The bias of a Boolean function expresses how 'imbalanced' a function is. In other words, how far away it is from a balanced function, i.e. one that is as  often 0 as it is 1. The bias $\mathcal{E}$ of an $n$-bit Boolean function $f$ can be computed using:

$\mathcal{E}(f) = \sum_{x\in\mathbb{F}_2^n} (-1)^{f(x)} = 2^n - 2\mathrm{hw}(f)$.

Here, $\mathrm{hw}$ denotes the Hamming weight of a function, i.e. the number of times a 1 appears. For example, $S_1(x)$ has a bias of 0, but $S_4$ has a bias of 2, as its Hamming weight is 7.

Linear cryptanalysis exploits the most biased linear relation between its input and output. However, it doesn't only consider the full input and the  full output, but sums of specific bits are selected in both the input and the output that have a strong bias. These bits are selected using masks $a,b$. The masks have a 1 for the bits that we want to consider and a 0 otherwise.

For any pair of masks $a,b$, the linear approximation table (LAT) contains the bias of $S_b + \varphi_a$, where $\varphi_a$ maps $x$ to $ax$. (The bias of this value is also often referred to as the Walsh coefficient of $S_b$ at $a$.)

Now for a concrete example: take $a = 12$, or $1100$ in binary, and $b = 1$, or $0001$ in binary. Then $\mathcal{E}(a,b) = \mathcal{E}(\varphi_a + S_b(x)) = \mathcal{E}(x_3 + x_4 + S_1(x))$. Because this is math in $\mathbb{F}_2$, these $+$'s should be read as XORs.

x      | 0 1 2 3 4 5 6 7 8 9 a b c d e f
----------------------------------------
x_3    | 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
x_4    | 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
S_1(x) | 0 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1
         ------------------------------- +
         0 0 1 1 1 0 0 1 0 1 1 1 1 1 0 1

The bottom row has a Hamming weight of 10, so $\mathcal{E}(a,b) = 2^4 - 2*10 = -4$.

Now if you look at the tutorial on page 11, there is actually the value $-2$ for an input sum of 0xC and an output sum of 1. This might have caused some confusion. Sometimes, all values are already divided by 2. Then it corresponds better to the probability, as the probability is now simply the number in the LAT divided by 16. It is a matter of definition  whether you prefer to have $+16$ in the top left ($a = 0, b = 0$) or $+8$, although I guess the latter is more common.

If you prefer to look at Python code, a very simple script (not mine) that computes the LAT can be found here.

I hope this answers your question.


Integrity protection in wireless sensor networks

That's a lot of questions, I'll try and answer in order.

A hash or message digest alone is not secure because anybody can calculate and thus substitute a hash value. If you (correctly) add a key to the mix then you get a HMAC, which can be used.
Nowadays often a HMAC is used, or an authenticated mode of authentication such as GCM, CCM (for packet encryption) or EAX. If you want to use a MAC based on a block cipher you can use AES-CMAC. You'll need a 128 bit block cipher though.
Yes, you should check if hashing or encryption is most efficient on your platform. You could also have a look which one is least vulnerable to side channel (timing / energy usage) attacks. You want to try and find the best crypto library available if you have only just seen crypto for the first time.
You already answered it. Although it is less a worry in HMAC, for AES-CBC-MAC and even AES-CMAC it is considered best practice to use a separate key for encryption and calculation of the authentication tag. Usually deriving an additional key is not that much of a performance issue. Note that it is strongly recommended to use a key for each direction as well, and to make sure your IV is unique (and - for CBC - unpredictable). Your MAC should include the IV, not just the ciphertext.
I think I just named 3 authenticated ciphers in answer 2), all of them use just a single key (externally, anyway) and auto-include the IV within the authentication. GCM and CCM are NIST standardized, EAX is a proposed mode to NIST but - as it simply uses AES-CMAC internally - it's very likely secure.


Diffie-Hellman key exchange, then so what?

The multiplicative DHKE and its Elliptic curve version ECDH can be used to establish a common secret between the parties. Once the key established, this key can be used to derive symmetric keys for AES-GCM, AES-CCM, and ChaCha20 which are the cipher suites in TLS 1.3. These ciphers are Authenticated Encryption with Associated Data (AEAD) and provides Confidentiality, Integrity and Authentication. In other terms, they provide the standard of IND-CCA2/NM-CCA2- ciphertext indistinguishability and non-malleability under adaptive chosen-ciphertext attack. Combining asymmetric with Symmetric encryption is called the hybrid cryptosystem and this is common practice. We prefer it since public-key cryptosystems are very slow compared to public-key encryption systems.
DHKE can be used static-static, static-ephemeral, and ephemeral-ephemeral. As of TLS 1.3, Static RSA and Diffie-Hellman cipher suites have been removed so that forward secrecy is now obligatory.
To derive a symmetric key a Key derivation Function can be used, it can be used even to derive multiple keys and IV/nonce. Once a key is derivation method is agreed on both sides, the sender can encrypt the message by one of the cipher suites of the TLS with the derived key and the other side can use the same key derivation to derive the key to decrypt.
Another example is the Integrated Encryption Scheme.


Can Elliptic curve Diffie–Hellman (ECDH) shared secret be used as a static encryption key?

This usage is theoretically sound assuming you do not desire Perfect Forward Secrecy, but will exacerbate attacks on the block cipher by providing potentially very many messages encrypted under the same key, and will exacerbate side channel attacks by repeatedly deriving the static secret (allowing many chances to catch small fragments and re-assemble).

Consider also that if users A and B have a static secret, then party C who obtains either A or B's key, can recover the shared secrets in both directions, and thus impersonate either party, to either party.

Edit: Another notable attack: party D, who does not have either key but can capture packets, can replay any message that A or B sent, and they can send it in either direction at any time, of course the keys will still be valid so the message will appear authentic. This can be just as effective as a full break in many cases.


Are there any elliptic curve asymmetric encryption algorithms?

As already mentioned in a previous comment, ECIES (a hybrid encryption scheme) is typically the way to go when implementing
asymmetric encryption on elliptic curves, as it is standardized. It provides chosen ciphertext security (IND-CCA).

But as you are looking for "pure" public key encryption schemes, here we go:

ElGamal can not only be implemented in (prime order $q$ subgroups of) $\mathbb{Z}_p^*$ for prime $p$, but equally
on elliptic curve groups. It provides chosen plaintext security (IND-CPA).

Furthermore, there are various ElGamal-type schemes I want to mention:

Cramer-Shoup is an ElGamal variant that provides IND-CCA security.
If you work in a pairing friendly elliptic curve setting,
it may be the case that in the group in which you are using the encryption scheme the decisional Diffie-Hellman (DDH) problem
is easy. In such a case ElGamal is insecure as it's security relies on the DDH. Here, you can use Linear-encryption, which in contrast to ElGamal relies on the decision linear (DLIN) assumption and stays secure even if the DDH is easy and is also IND-CPA secure.
There is also a IND-CCA secure Cramer-Shoup version of linear encryption (but that's rather of theoretical interest).
Furthermore, recently I encountered another variant of linear encryption, denoted as linear combination encryption (unfortunately, behind a paywall) which provides IND-CPA security and relies on the decision linear combination (DLC) assumption. It can also be used in groups where the DDH may be easy (however, this scheme is rather esoteric and seems to be tailored to the constructed group signature scheme and the proofs respectively).

The most efficient one of these schemes is the standard ElGamal version.


How many keys does the Playfair Cipher have?

When we consider that a Playfair key consists of the alphabet (reduced to 25 letters) spread on a 5x5 square, that's $25!$ keys (another formulation consider any string to be a key; then strings leading to the same square are equivalent keys).

The rules of Playfair are such that any rotation of the lines in the square, and any rotation of its columns, lead to an equivalent key (in other words, the square reduce to a torus). It can be proven conclusively that there are no other equivalent keys (note: a transposition of line/columns leads to a key such that 200 out of 600 digrams with distinct letters are mapped to the same diagram as for the original key, and the other 400 are mapped to the digram obtained by exchanging the two letters in the digram mapped by the original key; also, an horizontal or [resp. and] vertical mirroring of the square leaves 500 (resp. 400) digrams invariants; these are near-equivalent related keys, but not equivalent keys).

I conclude Playfair has $25!/{5^2}=620448401733239439360000\approx2^{79}$ distinct keys classes (a 79-bit-key cipher). At least another source agrees.

This is much less than an arbitrary permutation of digrams with distinct letters, which allows $(25\cdot24)!\approx2^{4678}$ keys.

If that's a homework question, I find it excellent to illustrate the notions of equivalent keys, key space, and why a big keyspace is not sufficient for security.


With AES_CMAC, tag truncation acts like you would expect; if an attacker generates a message and a random tag, then they have a $2^{-32}$ (or one in 4 billion chance) of happening to pick the correct random tag (and getting the message accepted), and with AES_CMAC, there's nothing they can do to improve on that.

Is a $2^{-32}$ success probability per attempt by the attacker acceptable?  Well, that depends on what your authenticating (and the cost to you of accepting an invalid message); in some scenarios, that might be quite acceptable, in others (e.g. doing financial transfers) it might not.


Differences between industrial and military cryptography

There’s no difference except for marketing. Neither of the terms has a meaningful technical definition on which a substantial share of experts in the field can agree.

Historically there was a difference in permissible key length due to U. S. export restrictions but those stopped a long time ago except for a few countries that are under broader embargo (e. g. North Korea, Iran, Syria).


Simple protocol for 1-out-of-2 oblivious transfer

There are two that I know of that are pretty simple.

I'll first start with one that requires a "Trusted Initializer" where we assume that there is a party Ted which is trusted by both Alice and Bob and only needs to be present for the initialization stage. This is an extension of a quantum protocol and was proposed by Rivest in Section 7.

Alice holds $m_0,m_1\in\{0,1\}^k$, Bob holds $c\in\{0,1\}$ and wants $m_c$
Ted privately gives Alice $r_0,r_1\in\{0,1\}^k$, chosen at random
Ted generates a private bit $d\in\{0,1\}$ and privately sends $d,r_d$ to Bob
Bob sends $e=c\oplus d$ to Alice
Alice sends $f_0=m_0\oplus r_e$ and $f_1=m_1\oplus r_{1-e}$ to Bob
Bob computes $m_c=f_c\oplus r_d$. About $m_{1-c}$ Bob learns nothing.

The second comes from Wikipedia where it is instantiated with RSA (so exponentiations are done in the RSA group parameterized by the public key).

Alice holds $m_0,m_1$, and an RSA key pair $(e,d,N)$. Bob holds the public key $(e,N)$ of Alice, $c\in\{0,1\}$ and wants $m_c$
Alice generates random $x_0,x_1$ and sends them to Bob
Bob chooses a random $k$, computes $v=x_c + k^e$ and sends $v$ to Alice.
Alice computes $k_0=(v-x_0)^d$ and $k_1=(v-x_1)^d$ and sends $m_0'=m_0+k_0$ and $m_1'=m_1+k_1$ to Bob
Bob computes $m_c=m'_c-k$ and learns nothing about $m_{1-c}$

You'll notice that the two protocols are somewhat similar which is kind of cool if you wanted to present both. The 2nd removes the assumption of a trusted initializer and replaces it with a public key pair for Alice.


How to prove a lemma that is based on phi-hiding assumption?

There exists a distinguisher that works with nontrivial advantage, $O(1/\log \phi(m))$.

This is because $q_0$ must be a multiple of $p_0$; however $q_1$ is a random value between $0$ and $\phi(m)-1$.

Hence, the distinguisher is "test both for primality, if one is prime, say that one is $r \cdot p_1 \bmod \phi(m)$"

$q_1$ is a random value, and hence it will be prime with probability $O(1 / \log \phi(m))$.

$q_0$ is a value $k p_0$, for a random $k \in (0, \phi(m)/p_0)$; hence it will be prime only if $k=1$, which happens with tiny probability $p_0 / \phi(m)$

$1 / \log(\phi(m)) \ggg p_0 / \phi(m)$, and hence this is an effective distinguisher.

If the adversary is given several rounds, say, multiple values $q_0, q'_0$ and $q_1, q'_1$, much better distinguishers can be constructed.


Subverting the key generation step in RSA public key cryptography

I don't think idea 1 can be made to work at all. The main point is that in order to generate a correct secret decryption key, the key generator must know the order of $\mathbb Z^*_n$, i.e., the totient of the modulus $n$.  The generator knows that $n=p \cdot q$, where it believes that $p$ and $q$ are primes, and so it believes that the totient is $(p-1)(q-1)$. But in reality, if $p$ is not prime, the actual totient must be smaller, because the totient of $p$ is strictly less than $p-1$ (and similarly for $q$). So the generator will not be working with the correct totient, and cannot compute a correct secret key. (Technically, all of this assumes that $p$ and $q$ are actually coprime, which the generator can check for itself.)

As for idea 2, it essentially has been implemented in practice, in the sense that several key-generation algorithms having that flaw were deployed and used for years without suspicion. The simplest explanation is that these were accidental rather than malicious flaws, but the same kind of flaw could be deployed maliciously as well.

UPDATE: the "problem" with subversion of type 2 is that the public can discover that many keys share a common prime, and thus learn of the subversion. Here is another kind of subversion that does not have the problem of shared primes, but does allow the subverter to factor the generated modulus. The subverter designs the generation algorithm to choose a prime that is close to the output of a PRF applied to (say) the email address and/or time of day -- some (quasi-)public information that will be associated with the key, which will be unique every time the generator is run.  So the chosen primes will likely never be the same, but the subverter can find them easily using the secret key of the PRF. The only catch is that the PRF secret key must also be hidden in the generator algorithm. A suspicious user might be able to discover the subversion by inspection or by running the algorithm in controlled ways, but not by discovering shared primes across keys (because they do not exist).


Probability of Repeated Encrypted Block In Output Feedback (OFB) Mode

Well, if the block cipher is modeled as a random $N$ bit permutation (that is, each permutation from the set of $2^N$ bit patterns to itself is equally probable), then the answer is really quite easy (and this answer is exact): the probability that we will repeat a block within $M$ outputs is precisely $(M-1) 2^{-N}$ (for $0 < M \le 2^N+1$).

The reasoning behind this is remarkably simple.  First, when we consider the sequence $X, P(X), P(P((X)) = P^2(X), P^3(X), ...$, we see that the first pair of repeated elements must include the starting point $X$.  Here's why: if we have the pair $P^i(X) = P^j(X)$ for $i, j \ne 0$, then we have $P^{i-1}(X) = P^{j-1}(X)$ (remember, $P$ is a permutation, that is, if $P(A)=P(B)$, then $A=B$), and so if we have a pair $i,j \ne 0$, that can't be the first pair.

Now, let us compute the conditional probability that, if we haven't had a repeat after $M-1$ outputs, we get a repeat after $M$ outputs.  Now, after we have cycled through $M-1$ outputs, there are $2^N - (M-1)$ outputs we haven't generated before and $1$ output that we have that might be generated in the next step (the other outputs we have generated are impossible, by the reasoning in the above paragraph).  If we've specified $(M-1)$ outputs of a permutation, the rest of the possible outputs are equiprobable, and hence the probability that we're generate the one output that would generate a repeat is $1 / (1 + 2^N - (M-1)) = 1/( 2^N-M)$

Now, the probability that we'll generate the first repeat at step $M$ is the probability that we'll not generate a repeat after $M-1$ steps, and then repeat at step $M$.  This is:

$Prob(M) = (2^N-1)/2^N \cdot (2^N-2)/(2^N-1) \cdot ... \cdot (2^N-M) / (2^N-M+1) \cdot 1 / (2^N-M) = 1/2^N$

That is, the probability that we'll get a repeat after exactly $M$ steps is independent of the value of $M$ (as long as it is in range).

And hence, the probability we'll get a repeat after $M$ steps (or earlier) is just the sum of the probabilities that we'll generate the first repeat after $k$ steps for $1 < k \le M$, and that's $(M-1)/2^N$.

If you insist on a link, you can look at this one; this uses different logic to come up with the same result.

If the block cipher cannot be modeled as a random permutation (or a random even permutation; that answer differs only in the $M=2^N$ case), well, I don't know on any specific study; that would probably depend on the specific block cipher, and how it differs from a random permutation.


How strong is XOR encryption of 256 bit plain text with 256 bit key?

That construction is called a one-time pad or OTP (not to be confused with a one-time password). OTP's are theoretically perfectly secure as long as the key is not repeated or reused and the key is indistinguishable from random by any adversary. In that case any 256 bit plaintext message is equally likely, so it is impossible to even brute force the key. Because of that, the size of the key and plaintext do not even matter, as long as there are as many bits for the key as there are bits in the plaintext.

Note that an OTP does not provide message integrity nor authenticity, only confidentiality. Of course the exact size of the input is leaked by an OTP too, so that's not kept secure either.

Of course, generally the practical security depends on the system, the quality of the randomness, the actual access to the key etc. etc. etc.


The Full Response has additional information over and above the P7B file with information such as the CMC response and some chaining information.  I'd go as far as to say it's not really relevant in day-to-day use.

You can look at them all with certutil.exe and make your own mind up though - simply pipe the outputs to a text file and read at your leisure. If the extra parameter to your command above is webapp.ful the following will allow you to read all of the files with a text editor:

certutil webapp.cer > cer.txt
certutil webapp.p7b > p7b.txt
certutil webapp.ful > ful.txt


What is 'Carry-forward verification' defense against MITM?

That was a bad edit to Wikipedia.  The phrase Carry-forward verification is not a standard, well-known term in the cryptographic literature.  It should not have been included in Wikipedia without a reference to something more specific.  But oh well, no one is perfect, sometimes these things happen.

Your request for an elaborate survey of MITM defense is most likely too broad for this site; the kind of defenses that are suitable are dependent upon the specific application domain.  You can read up about certificate authorities, web of trust, X.509, certificate pinning, trust-on-first-use (aka key continuity), and many other models.  There's lots written on this topic.


Is there any patent free EC point compression available? If not, should I GPL/LGPL my code?

Classic affine point compression, storing only the x-coordinate and a single bit of the y-coordinate, is claimed in two different U.S. patents:

US 6,141,420: “The inventors have also recognized that the bandwidth and storage requirements of a cryptographic system utilizing elliptic curves can be significantly reduced where for any point P(x,y) on the curve, only the x coordinate and one bit of the y coordinate need be stored and transmitted, since the one bit will indicate which of the two possible solutions is the second coordinate.” The patent expired in 2014.
US 6,252,960: claiming “1. A method of compressing elliptic curve data which includes X and Y coordinate data, the X coordinate data consisting of N bits and the Y coordinate data consisting of at least 1 bit, using (a) a generator polynomial, and (b) a digital processing computer with at least first and second registers, said method comprising:” The patent expired in 2018 and may have been invalid all along because of the patent above already outlining the idea.

The patents have all expired by now; there is no need to live in fear of point compression any longer.

Daniel J. Bernstein convincingly argued that there was prior art for point compression all along so that we wouldn't have needed to live in fear of the patents in the first place. But considering the patents are all expired now, this is all but irrelevant history. Ed25519, when introduced in 2011, had point compression (recovering the x-coordinate from a y-coordinate), and evidently no lawsuit followed.

Other, more elaborate forms of point compression for Edwards and Montgomery curves have been proposed as well, namely Decaf and Ristretto. They are not only more efficient (a compressed point takes one bit less than the bit length of a full coordinate to represent because only non-negative points are considered valid when decoding), but also guarantee landing on the prime-order subgroup when decoding. They have each been out there for over a year now and no patents applicable to them seem to exist. For the Decaf case, it seemingly spawned from a series of threads on the public moderncrypto curves mailing list in 2014 and the final paper in 2015, so that if a patent were filed, it'd have to take that prior art and discovery process into account; Ristretto itself builds on the ideas in Decaf.


Repeating something encrypted and non-encrypted?

No, it won't "leak" information, as long as you're using a modern symmetric algorithm that's resistant to known-plaintext attacks.

However, depending on the encryption mode used (and whether there's integrity checking or not), there can be other security implications, such as the data in the known spot being substituted.


How to ethically publish the result in case we prove that P = NP?

I'll try to answer what I view to be a much easier question to answer, while still (in my view) capturing the "essence" of the problem.

How can one "prove" that they have an efficient algorithm for an NP-complete problem without publishing the algorithm?

There are many things one can do, but the simplest is to solve challenges.
There are a large number of computational challenges which have been posted over the years, for example:

RSA factoring challenges

Lattice Crypto challenges

If one solved a variety of these challenges in extremely high dimension and posted the solutions publicly, it would very quickly erode confidence in the hardness of the underlying problems.
After waiting a suitable amount of time, you could then publicly post your algorithm.
Of course, it is difficult to talk about what a "suitable amount of time" is for public disclosure that would break all of cryptography, which is why I avoided your initial question.


How to prove that a committed value is the square of other

Yes there is - since any NP relation has a zero-knowledge proof of knowledge (assuming any OWF). Here, it's actually a standard and nice exercise, so I will give you a few hints (if you are stuck, I'll give you more hints):

Do you know how to prove knowledge of an opening to a Pedersen commitment? (hint: it's a straightforward generalization of the Schnorr proof of knowledge of a discrete logarithm)

Then if you know the above, the crucial trick is to rewrite $c_1=g^vh^{r_1}$ and $c_2=g^{(v^2)}h^{r_2}$ as $c_1=g^vh^{r_1}$ and $c_2=c_1^vh^{r_2-vr_1}$. Then, use the proof of knowledge of an opening to show knowledge of an opening of both commitments, to the same message ($v$), in different bases ($g$ and $c_1$).


No.

Something similar which might be confused:

If $M$ is an unknown message and you know $h = \operatorname{hash}(M)$ and $l = \operatorname{length}(M)$, then for many hash functions it is possible to calculate the hash $h'$ a message $M' = M\ ||\ P\ ||\ X$, with $P$ only depending on $l$ (and the hash function) and $X$ arbitrary chosen by me (or by someone else).

It is still necessary to know $X$ to do the attack, mere knowledge of $\operatorname{hash}(X)$ doesn't help.

This attack (length extension) applies to many older hash functions, including MD5, SHA-1, and all hashes of the SHA-2 family. It doesn't apply to any of the SHA-3 candidates (because resistance against this was a criterion).


Does a man-in-the-middle attack apply in this scenario?

The exercise fails to cover how a sender is supposed to know the Id of an intended recipient, and how the CE is supposed to know that a KiPub it gets is that of the Mi with this Id. If the goal is just to get away with a high mark, ignore the issue or briefly mention we assume sender knows Id; and CE knows Id and KiPubwith, and acts honestly. Never insist that the question is lacking when it could be that the author is the grader!
Then the initial answer to (a) is correct: with only passive eavesdropping, there's no attack to the system proposed. I don't get what's meant by "formally" incorporated, but a Man in the Middle is an adversary assumed to go beyond passive eavesdropping, and that's excluded in (a) by "cannot meddle with the contents".
For (b), there's an attack possible by a MitM. Just describe that attack with enough details, like you are the mastermind explaining how it's done to a novice accomplice. Detail exactly what the MitM changes (and into what) in order to "decrypt the messages sent" [hint: "The message" won't cut it].
For (c), "every node stores every other node's public key" is a solution to the attack in (b) only inasmuch as it gets achieved, and the question asks how. One acceptable answer involves detailing how the CE makes public key certificates, how they are communicated and checked. I recommend to make another assumption explicit: that each member knows the CE's public key.
More hint: the first part of (c) ask how we prevent the attack in (b), and in my reading that requires explaining how we get a member to know another member's KiPub, rather than assuming that it happens [it did not in the attack of (b)]. Among the methods for this allowing new members (as required), matching (c), and close to the practice commonly taught, we'd rather use the one closest to the exercise's existing setup. That seems to be: keep the CE authenticating new members and their KiPub however it does that now, and tweak it's role: from distributing a KiPub on request, to distributing certified KiPub to each existing member as a new member enrolls.
The part of (c) about the storage required may be calling for a comparison with the storage required for secret-key cryptography, and a level of criticism of "every node stores every other node's public key".


How do I store encrypted files on a web server and decrypt them locally?

You were doing fine up to the point where you wrote "JavaScript".

Of course, JavaScript as a language is not fundamentally unusable for crypto (although, as a high-level scripting language, any crypto primitives implemented in JavaScript are likely to be rather slow and hard to secure against side channel attacks).  However, when you write "JavaScript", I assume you mean code sent by the server and executed on the client by a browser.

This security model is fundamentally flawed for two reasons:

first, if you're not using HTTPS, then anyone who can intercept the communication between the client and the server (by, say, ARP or DNS poisoning, or a rogue WiFi access point) can modify the code sent to the client and insert their own back doors; and
second, even if you do use HTTPS to secure the connection between the client and the server, the client is still blindly executing any code given to it by the server.

If your goal, as you write, is to prevent the server from learning or tampering with the data by encrypting it on the client side, then you haven't really accomplished anything of the kind: the encryption may be done on the client, but it's done using code sent by the server, and there's nothing preventing that code from storing the user's keys and passwords and hiding them among data sent to the server.

(Of course, a careful inspection of the code and the network traffic it generates might uncover such back doors, but most users will be neither able nor willing to carry out such an inspection.  And it's not enough for just one or two users to do it, since the other users have no reason to trust that the code they've been sent is the same as the code that's been sent to others.)

For more information on why this is a bad security architecture, see e.g. this post from Bruce Schneier's blog and the articles linked from it.

OK, so what should you do then?  Well, if you want to run some JavaScript (or other) code on the browser without the server having full control over it, you could make it a browser plug-in that the user can install.  This still won't be entirely secure, since the plug-in itself could be compromised, but at least it limits the attack surface a little.  (Of course, you should probably make sure the plugin isn't able to silently upgrade itself, since that would just reopen the hole completely.)

You can also try publishing cryptographic hashes (e.g. SHA-256; not MD5, that's broken) of your code to allow users to verify that it hasn't been tampered.  Of course, if I download both the code and the hashes from your site, you (or an attacker in between, if you didn't use SSL) might have tampered with both, but at least, if I was careful and paranoid enough, I could in principle look for copies of the hashes elsewhere (e.g. Google's cache) to be sure that I've got the same software that others have.

The bottom line, though, is simply that it's really hard to provide a crypto service which is secure against the potential compromise of the service provider itself.  You can either do your very best, and inform your users about the remaining holes — or you can give up, do the crypto on the server and just use SSL for transmitting the data (and maybe hint at users that they may want to encrypt their data locally first, just in case).  But please don't try to fool your users with insecure half measures like in-browser JavaScript crypto.

Ps. Rereading your question, I notice that you did address, or at least wave your hands at, this issue at the end.  Still, my point stands.  Compared with the big glaring hole of running potentially untrusted crypto code, I see no obvious flaws in any of the rest of it.

Anyway, given that PBKDF2 is (deliberately) slow, especially in JavaScript, you'll probably want to minimize the number of times a legitimate client needs to execute it.  So I'd suggest something like this:

Let $P$ be the user's password.  When the user enters it, the client hashes it into a 128-bit key $K_P = \text{PBKDF2}(P)$ (preferably salting it with some user-specific value).
When each file is encrypted, a random 128-bit key $K_F$ is generated.  The file is encrypted using AES in a suitable mode (not ECB) with the key $K_F$ and sent to the server.
The client encrypts $K_F$ with $K_P$ using AES in ECB mode (which is OK, since we're just encrypting a single 128-bit block), yielding $C_K = \text{AES}_{K_P}(K_F)$.  It also encrypts $K_F' = K_F + 1$, where $+$ denotes addition modulo $2^{128}$ (or even just modulo $2^{32}$ or $2^8$, with the remaining bits untouched), yielding $C_K' = \text{AES}_{K_P}(K_F') = \text{AES}_{K_P}(K_F + 1)$.
The client sends $C_K$ and $C_K'$ to the server, which stores them in the index.
When the client wants to decrypt a file, it first downloads the index, decrypts $C_K$ and $C_K'$ to get $K_F$ and $K_F'$, and checks that $K_F' = K_F + 1$; if not, it asks the user the confirm that the password is correct.
If the check passes, the client now knows $K_F$, and can download and decrypt the file.
If the user wants to change their password, the client just needs to recompute $C_K$ and $C_K'$ for each file and send the new values to the server; the file keys $K_F$ need not be changed, and thus the files themselves need not be re-encrypted (although it's nice if the client does provide that option too, in case the users suspects the file keys may have been compromised).


Why is the point at infinity on Edwards Curve different to Weierstrass curves?

In mathematics, every group need and identity element. The points on the elliptic curves forms a group. Therefore they need an identity element, too.
The identity element is determined by the addition law of the curve. Some curves need a point at infinity $\mathcal{O}$ as the identity element (neutral element).
In the Edwards curve, the neutral element is chosen as $(0,1)$ and this can be represented in the affine coordinates. Other coordinate like $(0,-1)$ can be identity, however, this requires different formulas.

If I understand correctly, the identity point on all elliptic curves is the point at infinity.

No not necessarily. Edwards curves doesn't need a point at infinity.

But on the Edwards curve, this can be written in Affine form?

Yes, it is $(0,1)$

Does this have something to do with the fact that Edwards curve formulas are complete?

No, it is just by the equation of the curve and the defined addition law. This is very similar to the analogous to clock

What would the point (0,1) be on the Weierstrass curve signify? If b=1, then we can represent this point on the Weierstrass curve?

Converting formulas exist like this one

Fast Algorithm for Converting Ordinary Elliptic Curves into Binary
Edward Form

it still has not clicked with me, the fact that the point at infinity is in the group, yet it cannot be represented? But somehow it can b represented on the Projected form, which is another form of the same curve? Whereas Montgomery is a different curve entirely?

An birationally equivalence doesn't say about the representation of the elements. Consider the isomorphism of two group, they are same but they can be completely defined over different sets.
The the neutral element can be defined but you force it to be defined over the affine coordinates. Some curves need the protective coordinates so that every element can be represented with some coordinates.


Is modern encryption needlessly complicated?

The main difficulty with the one-time pad is that it requires pre-arrangement. In order for me to use a one-time pad to communicate with you, we must either have arranged ahead of time for a one-time pad that we will use (which must be as large as our communication will be), or else we must have some secure way of communicating that will allow us to agree on a one-time-pad for use.

If we have a secure channel to communicate so we can agree on a one-time-pad, then why bother? Let's just communicate through the secure channel.

If we don't have a secure channel, then we cannot engage in secret communication ex-nihilo, since we will not have a one-time-pad agreed on.

Now, if you are going to generate the one-time-pad via a pseudo-random number generator, how are you going to get that one-time pad to me? You must tell me your seed (so that I can generate the same pseudo-random sequence and I can decode the message), in which case we are back to the problem of how you tell me what your seed is without a secure channel to communicate with. So now we have two points of vulnerability: the channel we use to communicate so you can give me the seed; and the fact that a pseudo-random number generator is not truly a random number generator, and so may be susceptible to attack as well.

There is also the problem of distribution; to use one-time pads effectively, no pad can be used more than once. There were intercepts that the NSA had from back in the 50s; when the Soviets mistakenly used the same one-time-pads to encode some messages in the 80s, this was enough to break the encryption in both cases. That means that each message will need a new seed and a new password; so each time you want to communicate you need a new seed/key and a new password. It is just too easy to lose the information, or to re-use it by mistake and thus make the entire thing a wash.

One time pads are effective for pre-established channels of communication with low bandwidth; they are almost useless for initiating remote secret communication with someone you have never communicated with before, and they require a lot of bandwidth to use correctly.


About the necessity simulators set adversary random-tape

In the vast majority of cases, the simulator sets the random tape of the adversary simply because it has to (by the definition). So, the simulator sets it in the beginning to be uniform, and this is then ignored from then on.

There is one cases that I know of that this is actually really important, and this is non-black-box zero knowledge. Specifically, in Boaz Barak's thesis, he has a number of constructions. The construction which works for uniform verifiers has the property that the verifier has to have a short description. In order to make this work, the random tape of the verifier is actually chosen by the simulator pseudorandomly (rather than truly randomly) since this then has a short description.

I don't know of anywhere else that this is important. In general, choose it at random and ignore from then on...


From a quick read, there are a couple of potential issues.

decrypt_128_256 is iterating rounds in the same order as in encrypt_128_256, so the round keys are being applied in the wrong order on decrypt.
decrypt_128_256 needs to iterate through the round keys starting from the last round and working backwards.
68 rounds are being used for Speck128/256 (should be 72) - this won't stop it being symmetric, but it will stop it passing test vectors.

A reference you can run against is a really good idea - I tend to instrument all of the intermediate calculations on the reference and new implementations, pipe both sets of output to files and diff the output to see where things need fixing up.

As you've discovered the Simon/Speck algorithms are a wee bit short of reference code - I managed to bootstrap off the Speck128/128 example at the end of the spec to a working implementation of the Speck variants, and Simon was straightforward after that.

I've just pushed my Java implementations of Simon (and Speck), which you can use for comparison or runtime reference (it's in a feature fork of Bouncy Castle, so you should be able to build from the root with little trouble).


Are there Cryptography certifications variants of CISSP?

The EC Council offers some certification although I have no idea who they are. I think CISSP implies you know about cryptography because you get examined on it although I don't know the depth they go into.

Other than that a Uni degree in security or cryptography would fit the bill, or a certificate from Coursera or related services, although that's of course not as prestigious as CISSP.


Stretching a random seed to maximize entropy

What you ask for is a RNG to produce some output which another RNG will use as seed. This looks quite overly complex...

The point of the seed is to be unknown to the attacker: the seed data should be such that "trying out" possible seed values should not match the actual seed except with negligible probability. With a 64-bit seed, even if the seed is "perfect" (chosen totally randomly and uniformly among the $2^{64}$ possible seed values), an attacker trying possible seed value still has a $2^{-64}$ probability of finding the correct seed at each try, and that's a bit high for comfort. We usually prefer attack probabilities of $2^{-128}$ or less. Regardless of how you generate your 64-bit seed, how you then expand that 64-bit seed into whatever ISAAC requires, and whether ISAAC is good or not, your security will never be higher than that provided by a 64-bit seed.

How ISAAC is supposed to be seeded (with what, under which properties) is not clear; the ISAAC author himself says:

  I provided no official seeding routine because I didn't feel competent to give one. Seeding a random number generator is essentially the same problem as encrypting the seed with a block cipher. ISAAC should be initialized with the encryption of the seed by some secure cipher. I've provided a seeding routine in my implementations, which nobody has broken so far, but I have less faith in that initialization routine than I have in ISAAC.

Come to think of it, this is a bit scary comment. Are you sure you want to trust the security of a system, a part of which being deemed by the author himself as being not trustworthy ?

And more generally, ISAAC was designed at a time where the competition was RC4, a generator with known biases, and not that fast. Science has improved since. See the eSTREAM project: this is the result of a kind of open competition, where cryptographers proposed new stream cipher designs, and tried to break the proposed designs. The resulting "portfolio" consists in the designs which resisted cryptanalysis, and offer good performance. The good thing about these stream ciphers is that they work with keys of reasonable size, with no underspecified part as the seeding in ISAAC. For instance, consider Sosemanuk: it accepts a key of 1 to 256 bits, and a 128-bit IV, and produces pseudo-random bytes at an reasonably high speed (it should be competitive with ISAAC, possibly even a tad faster).

This would lead to the following design:

Accumulate your source entropy in a buffer. It does not really matter how you encode each metric, as long as you do not lose information.
Hash the whole buffer with a secure hash function, preferably SHA-256. This results in a 256-bit value.
Use the 256-bit value as key for Sosemanuk (the IV can be 0). Produce random bytes. Enjoy.
(Alternatively, use the Sosemanuk output as seed for ISAAC, if you really need, for administrative reasons, to use ISAAC. But the under-specification of the seeding process could trigger weaknesses, so I would not recommend it at all.)

Note that entropy gathering is a subtle thing. MAC address and system clock, for instance, are really bad entropy sources because they can be observed by attackers: the system clock is close to the current time, which (by definition) is public data, and the machine will write its MAC address on every ethernet frame it emits. Entropy is good only insofar as it is unknown to the attacker. The good thing about SHA-256 is that it does not matter if some of your entropy is bad, as long as there is also some good entropy somewhere in your buffer. Still, you are warmly encouraged to use as entropy sources the services specifically offered by the operating system to that effect (it is called CryptGenRandom() on Windows, /dev/urandom on Unix-like systems and MacOS X): since the OS directly manages the hardware, it is in ideal position to gather entropy from hardware sources.


is it necessary to write C=E(K,P), Can we write C=E(P,K)?

Personally I keep to what I do during development: the variable that is most static is to the left, the more dynamic ones to the right. So I use key, IV and input in that particular order.

A cipher is a keyed permutation, often written as $\text{E}_K$, so in my opinion $\text{E}(K, M)$ is closest to $\text{E}_K(M)$. Writing the parameters in a different order is not as nice. But as in any mathematical function, it is up to you to define it.

As Geoffroy said, if it is made clear then you can certainly get away with it. But I still would keep to the most common order if just to avoid confusion.

Oh, I just noticed that you use $P$ for "plaintext" while I use $M$ for "message", but that's really not much of an issue in my opinion.


How to deliver an encrypted message to multiple recipients without revealing keys

Also, if I give people the private key, and I keep the public key safe, am I right in believing that it's possible to generate a new public key just using the private key itself?

Correct. The private key contains the modulus, one or more of the primes, the private exponent and often some other relevant things. The public key is just the modulus and the public exponent, which is usually a small number, often 65537, and can be calculated with the private key even if it isn't.

What you actually need for your problem is authentication. You sign the data (e.g. with RSA-PSS), which you may have encrypted (whether with a symmetric key that you give the recipients or their public keys). The data can even be public if its secrecy does not matter.

The recipients can then use your public key (which they must somehow get first) to verify that the data was signed with your private key. Assuming you do not reveal your key, no one else can forge a valid signature.


why we are allowed to replace PRF with random function in security proof?

That's just how security proofs for these kinds of Feistel schemes work - you say something about the cipher when the round function is a truly random function, then you argue that because a PRF is indistinguishable from a random function for a computational adversary, the security proof still holds when your round function is a PRF. I think they use this technique in the original Luby-Rackoff paper, too.


You say DER, but you tag PGP which doesn't use DER -- and whose publickey block includes a lot of things beyond the RSA values (n,e). The DER encoding of a PKCS#1 RSA publickey of 4096 bits with a conventional e of 65537 (default at least for openssl and Java) is

30 82 02 0a   02 82 02 01 (n with leading 00)   02 03 01 00 01

with a total length of 526 octets. The DER encoding of a generic SubjectPublicKeyInfo which is always used in X.509 certificates and often in other places (including openssl and Java) adds an outer SEQUENCE and AlgorithmIdentifier and a wrapping BIT STRING giving a total length of 550 octets. If you mean something else, specify it more clearly.

For the private exponent see RSA: Most significant key bit always 1? .

But if you are concerned about the encoding of a private key, that is much more than just the exponent and (possibly) modulus; see https://stackoverflow.com/questions/5403808/private-key-length-bytes . In addition the privatekey is often encrypted, which usually expands the encrypted value and adds metadata about the encryption.

If you have a question about a particular key encoding with a particular program or protocol/format, you need be much more specific.


How to multiply a matrix of bits with another?

Multiplication of bits matrices works just like multiplication of number matrices, except the rule of addition is modified to: $1+1\mapsto 0$.

Let $U$ (resp. $V$) be a square matrix of $n\times n$ elements noted $u_{l,c}$ (resp. $v_{l,c}$) with $1\le l\le n$ and $1\le c\le n$. The product $U\cdot V$ is a square matrix $W$ of $n\times n$ elements noted $w_{l,c}$, with
$w_{l,c}=\sum_{j=1}^n u_{l,j}\cdot v_{j,c}$

In the problem at hand, $n=4$. To compute the bit at (say) the third line and first column in the result, we'll use the above formula with $l=3$ and $c=1$, giving $w_{3,1}=\sum_{j=1}^4 u_{3,j}\cdot v_{j,1}$, that is $w_{3,1}=(u_{3,1}\cdot v_{1,1})+(u_{3,2}\cdot v_{2,1})+(u_{3,3}\cdot v_{3,1})+(u_{3,4}\cdot v_{4,1})$. The third line of the left matrix gives $u_{3,1}=1$, $u_{3,2}=0$, $u_{3,3}=0$, $u_{3,4}=1$. The first column of the right matrix gives $v_{1,1}=1$, $v_{2,1}=0$, $v_{3,1}=1$, $v_{4,1}=1$. Thus $w_{3,1}=(1\cdot1)+(0\cdot0)+(0\cdot1)+(1\cdot1)$. That simplifies to $w_{3,1}=1+0+0+1$, then $w_{3,1}=0$.


RSA: Private key calculated from public key?

When p and q are primes and  n = p$\cdot$q ,  one will have

{p,q}    =    $\bigg\{\hspace{-0.06 in}n\hspace{-0.04 in}+\hspace{-0.05 in}1\hspace{-0.05 in}-\hspace{-0.03 in}\phi(n)\pm \sqrt{\left(n\hspace{-0.04 in}+\hspace{-0.05 in}1\hspace{-0.05 in}-\hspace{-0.03 in}\phi(n)\right)^{\hspace{.04 in}2}-(4\hspace{-0.04 in}\cdot \hspace{-0.04 in}n)}\hspace{-0.05 in}\bigg\}$   ,

so for semiprimes, computing $\phi$ is equivalent to factoring.

The above reasoning doesn't work for multi-prime RSA, but even there, there's no obvious way for the adversary to compute $\phi$ of the modulus more easily than just factoring the modulus.


Use of ElGamal encryption for signature generation

Because the function used for RSA encryption and decryption is commutative. This means that given secret key $sk$ and public key $pk$ for all messages $m$ you have that $$D(E(m,pk),sk)=E(D(m,sk),pk)=m.$$ This means that first encrypting a message with the public key and then decrypting the so obtained ciphertext with the corresponding secret key yields the same as first decrypting a message with the secret key and then encrypting the result with the corresponding public key.

Since the RSA function enjoys this property, one can obtain a public key encryption scheme and a signature scheme using the same function (I ignore padding and stuff like hashing and speak only of textbook RSA). Due to this property, people often wrongly say that in general signing a message is identical to decrypting (often also encrypting) with the secret key.

However, this property does not hold for ElGamal, where the public key encryption scheme and the signature scheme are very different.


What's the difference between a hash chain, transaction chain and a blockchain?

A hash chain is a sequence of hashes of blocks. Each block consists of the hash of the previous block, and (optionally) some data. These can be seen a special case of a Merkle Tree, that is one with only a single branch.
A transaction chain is a hash chain with the data being lists of transactions, instead of arbitrary data.
A blockchain is a Merkle Tree with a consensus algorithm to determine which branch is the "correct" one. Typically other branches get discarded, but not always. E.G. git uses a Merkle Tree internally to verify the directed acyclic graph of commits, with a specially named branch (usually master or main) maintained by some user as the cannonical chain.
Cryptographically they're all identical, unless the consensus algorithm of a blockchain involves cryptography. Not all of them do, eg permissioned blockchains simply require authorization by the chain administrator to add a block.