Correct way to map random number to defined range?

Let $m = Y-X$. Generating a random integer in the $X$ to $Y$ range is equivalent to generating a random integer in the $0$ to $m$ range (if you generate $r$, then just use $r+X$). For ease of notation, I assume that the low boundary is included and the high boundary is excluded (you want a random $s$ such that $X \leq s \lt Y$).

In most cases, you cannot get a truly uniform random generation by processing a fixed number $n$ of 32-bit integers. Indeed, $n$ 32-bit integers represent exactly $2^{32n}$ possible outcomes. If $m$ is not a power of $2$, then $2^{32m}$ cannot be divided into $m$ sets of identical cardinal.

The usual method is a rejection process:

Let $u$ be such that $2^u \geq m$.
Let $t = m \times \lfloor \frac{2^u}{m} \rfloor$.
Generate $x$, a $u$-bit value (from your generator of 32-bit integers, just append 32-bit values until you reach the size $u$ or more, and truncate to $u$ bits). We have $0 \leq x \lt 2^u$.
If $x \geq t$ then loop to the previous step.
Return $r = x \mod m$.

The idea of the method is that the $2^u$ range is split into a sub-range of size $t$ (a multiple of $m$) and another sub-range (of size less than $m$). If the $u$-bit value $x$ fall in the first sub-range, then you take it modulo $m$, which yields a uniform value since $t$ is a multiple of $m$. Otherwise, you just discard $x$ and try again. With the constraints above, it can easily be seen that the probability of $x$ falling in the wrong sub-range is less then $0.5$, so the average number of invocations of the PRNG will be less than $2$ (less than two invocations for a $k$-bit integer, which may involve a lot of invocations of the underlying PRNG which produces only 32 bits at a time, depending on your parameters).

Then you have a choice, namely what $u$ to use. One extreme is to use the smallest possible $u$, i.e. $2^{u-1} \lt m \leq 2^u$. This is the choice that maximizes the average number of loops; however, it means that the final "modulo" operation is a no-operation (with $u$ as small as possible, you have $t = m$). For small parameters ($m$ is less then 32 bits), this is often an appropriate choice, because PRNG invocations are usually cheaper than integer division (if you use an efficient PRNG, such as these ones, of course).

The other extreme is to make $u$ much bigger, so that the probability that $x$ falls in the wrong range becomes negligible; at that point, you can often just skip the computation of $t$ and the test $x \geq t$, and proceed directly to the modulo operation: this will imply a slight bias, but a bias lower than what can be detected, let alone be acted upon.

See DSA, annex B.2: for each DSA (or ECDSA) signature, a new value $k$ must be generated for each signature, in the $1$ to $q-1$ range (inclusive), and it must be as uniform as possible. The annex presents the two methods, one with 64 bits of extra space ($u \geq 64 + \log q$), the other with the smallest possible $u$. Which one is preferable is a question of performance and convenience; a DSA implementation (as opposed to ECDSA) must have some code to reduce big values modulo $q$, so using the extra bits is probably simplest; ECDSA implementations, on the other hand, especially hardware implementations which work with binary fields, will probably prefer the "small $u$" method. For security, both are safe.


What does the linear assumption over bilinear groups mean?

The problem you are referring to seems to be the Decisional Linear Assumption (DLIN), which states that given $(u,v,u^a,v^b)\in \mathbb{G}^4$, it is hard to distinguish a couple $(h,h^{a+b}) \in \mathbb{G}^2$ from a totally random couple $(h,h') \in \mathbb{G}^2$.

There is also the Computational Linear Assumption (CLIN), which states that it is hard to  compute $h^{a+b}$ given $(u,v,u^a,v^b,h)$.

The Decisional Linear Assumption is a weaker assumption (in the sense that it's harder to break) than Decisional Diffie-Hellman Assumption (DDH), so it can come in handy when DDH does not hold, which often happens in pairing-based cryptography.
According to this paper (page 9), we even have the following reduction :
$$DDH < DLIN < CLIN < CDH$$

I tried to sum up what I found but I'm not an expert in pairing-based crypto so I hope everything was correct.


Are there any known values for common hashes known to have no preimage

This is mostly answered (in the negative) in Do well-known hash functions have any "impossible" output values?.  Cryptographic hashes typically don't have enough mathematical structure to talk about things like the number of pre-images a particular value has.  You can do much better analysis of some non-cryptographic hashes like CRC32, since they have so much mathematical structure. In general, uniformly covering the full domain is a design goal, so the property you are asking about would be seen as a weakness.

Of course, it's not hard to design a hash with the property you are looking for.  Given any hash function $h(x)$ you can define

function H(x) {
    var count = 0, result = 0;
    do {
        result = h(x . count);
        ++count;
    }
    while (result == 0);
    return result;
}

Essentially you are just re-hashing any time you would return the "reserved" value.

All that said, the typical way to solve this problem from an engineering standpoint is to use a value definitely outside the set of possible values, like NULL.  This has the advantage that it survives changing your hash functions.


Decrypting Ciphertext with partial Key Fragment using LFSR and Berlekamp-Massey

TL;DR:
If you have a similar question, then use the online Berlakamp-Massey algorithm to get the minimal polynomial by providing the given keystream, then get the C++ code from github and then replace your tap positions, seed, and ciphertext and then compile and run.

The answer is attraction
How to get it
What is given: We have given the following information;

Key fragment
seed
ciphertext

Attack idea: The key fragment is given to calculate the shortest LFSR that outputs the given key fragment. Once you get the taps, initialize the LFSR with the seed then decrypt the ciphertext stream.
Steps in details;

Use Berlakamp-Massay algorithm to find a shortest LFSR (need not to be unique). An online version is used.

The output is given as $x^{16} + x^{12} + x^3 + x^1 + 1$

As noted on the online site the size of the LFSR is 16 and the tap positions are
0,1,3,12
  xxxxxxxxxxxxxxxx <-|
  || |       |       |
  ++-+-------+-------|
  01 3       12

Initialize the LSFR of size 16 with the seed and this tap positions. Run the LFSR and get the keystream;
11001010011101010101100010111110110000000011011000100011110101100001101101111101

X-or the keystream with the ciphertext

Convert the plaintext to ASCII to get
attraction

note 1: if you x-or the 16-bit seed with the ciphertext you will get the at. This has a very low probability to contain two letters from the English Alphabet. If we assume that only small English letters are used then the probability is $26^2/256^2 \approx 1.031\%$. This was the actual clue int the question. And, normally, real stream ciphers don't start immediately form the initialization. They step for a certain amount from the beginning.
note 2: A sample C++ code can be found in the github.


Can we use the authentication tag as Nonce / IV for the next message?

The authentication tag in GCM is generated by XORing a block cipher output with the Galois field hash (and truncating it for shorter lengths). It is thus assumed to look PRF. So it is effectively just a random nonce that should not collide until a birthday bound of $2^{t/2}$.

With a tag length of 96 or more bits, it should be secure. Shorter random IV lengths are prohibited in SP 800-38D. However, that standard also limits you to using the key no more than $2^{32}$ times, when using a random IV.

(Even though the nonce is "controllable" by an attacker with a chosen plaintext attack, that does not allow generating a collision except randomly. Otherwise it would lead to a forgery attack.)

I would still prefer a counter.

  For me it looks like it should be safe as the first chunk is standard GCM and every following one is indirectly based on the exact same nonce.

Note that this dependence means two things:

You need the tag from the previous chunk to decrypt the next one, so parallelization is slightly more difficult. (E.g. both processors would need to read the same memory location.)
If some chunk does not authenticate, you cannot trust that it's the only one that has changed. An attacker who changed chunk $i$ could also remove any number of chunks after it without that fact being visible. (With counters you can detect a localized change and still authenticate the rest as being in the correct place.)


You should packetize, or recordize, the messages into discrete units of a size reasonable for your protocol. Each record should be independently encrypted with its own IV. As an example, look at TLS 1.2 record or IPsec ESP packets. If a record is corrupted it can be discarded without impacting other records.

EDIT:

As pointed out by @poncho, TLS incorporates an implicit sequence number in the MAC calculation. Thus this may not be a good example. He also points that DTLS includes an explicit sequence number, and thus may be a better example.


What encryption should I use: Blowfish, Twofish, or Threefish?

TL;DR: Twofish and Threefish are fine.
It is not the best idea to have the cipher you want to use hardcoded because you can't upgrade easily when one of them is broken. to quote mikeazo in the comments:

What you should do is develop your application to not be bound to a specific cipher.

Twofish

In 1999, Niels Ferguson published an impossible differential attack that breaks six rounds out of 16 of the 256-bit key version using $2^{256}$ steps.

As of 2000, the best published cryptanalysis on the Twofish block cipher is a truncated differential cryptanalysis of the full 16-round version. The paper claims that the probability of truncated differentials is $2^{−57.3}$ per block and that it will take roughly $2^{51}$ chosen plaintexts (32 petabytes worth of data) to find a good pair of truncated differentials.

Bruce Schneier responds in a 2005 blog entry that this paper does not present a full cryptanalytic attack, but only some hypothesized differential characteristics: "But even from a theoretical perspective, Twofish isn't even remotely broken. There have been no extensions to these results since they were published in 2000."

https://www.schneier.com/academic/twofish/
https://www.schneier.com/blog/archives/2005/11/twofish_cryptan.html
Threefish

In October 2010, an attack that combines rotational cryptanalysis with the rebound attack was published. The attack mounts a known-key distinguisher against 53 of 72 rounds in Threefish-256, and 57 of 72 rounds in Threefish-512. It also affects the Skein hash function. This is a follow-up to the earlier attack published in February, which breaks 39 and 42 rounds respectively. In response to this attack, the Skein team tweaked the rotation constants used in Threefish and thereby the key schedule constants for round 3 of the NIST hash function competition.

In 2009, a related key boomerang attack against a reduced round Threefish version was published. For the 32-round version, the time complexity is $2^{226}$ and the memory complexity is $2^{12}$ for the 33-round version, the time complexity is $2^{352.17}$ with a negligible memory usage. The attacks also work against the tweaked version of Threefish: for the 32-round version, the time complexity is $2^{222}$ and the memory complexity is $2^{12}$ for the 33-round version, the time complexity is $2^{355.5}$ with a negligible memory usage.

http://www.skein-hash.info/ (the design of Threefish is based on it).
Blowfish

At this point, though, I'm amazed it's still being used. If people ask, I recommend Twofish instead.
— Bruce Schneier, Blowfish's creator, 2007

Swordfish
                         GABRIEL
              Here's the deal. I need a worm,
              Stanley. A hydra, actually. A
              multi-headed worm to break an
              encryption and then sniff out
              latent digital footprints
              throughout an encrypted network.

                            STANLEY
              What kind of cypher?

                            GABRIEL
              Vernam encryption.

                            STANLEY
              A Vernam's impossible. Its key
              code is destroyed upon
              implementation. Not to mention
              being a true 128 bit encryption.

                            GABRIEL
              Actually, we're talking 512 bit.

source


message with small order in RSA signature

The order $o$ of an element $m\in(\mathbb Z/pq\mathbb Z)^\times = (\mathbb Z/p\mathbb Z)^\times\times(\mathbb Z/q\mathbb Z)^\times$ is the least common multiple of its (multiplicative) orders modulo $p$ and modulo $q$.

If this order $o$ is known to the attacker (or at least small enough that one can find it, e.g., by baby-step giant-step), then the attacker can factor $N=pq$ if the multiplicative order of $m$ modulo $p$ differs from its order modulo $q$: The attacker raises $m$ to the power of $\frac{o}{r}$ for all prime factors $r$ of $o$, until modulo one prime factor of $N$, but not the other, the order of $m$ divides $\frac{o}{r}$, which can be detected by $0<\mathrm{gcd}(m^\frac{o}{r}-1\bmod N, N)<N$, breaking the RSA.

So what you are asking for allows the attacker either to break RSA or to find an element $m\ne 1$ that has simultaneously the same small multiplicative order $o$ for unknown primes $p$ and $q$ given just their product $N$, which I'd expect to be a hard problem ($m$ is modulo $p$ a $(\frac{p-1}{o})$-th, modulo $q$ a $(\frac{q-1}{o})$-th power).


How would I prove a number is not within a range?

You can achieve that by combining two range proof with an OR proof.

Specifically, given a commitment $c$ to a secret number $x$, you would prove the statement: ($x > 200$) OR ($x < 0$). Each of the two statements can be proven using any standard $\Sigma$-protocol for range proofs (see e.g. my answers here and here), and there are standard methods to construct a $\Sigma$-protocol for the OR of two statements given a $\Sigma$-protocol for each of the statements. You can find simple explanations about how this works by reading Section 3.5.1.2 of my PhD thesis.

For your second question, the usual strategy is as follows: you have a homomorphic commitment (e.g. a Pedersen commitment) to a value $v$ over $\mathbb{Z}_p$, where $p$ is a prime, and you want to prove that it is not equal to $x$. To do so, compute $m = (v-x)^{-1} \bmod p$ and commit to it. Note that $v-x$ has an inverse modulo $p$ if and only if $v \neq x$. Then, prove that the committed value $m$ was correctly constructed by proving that $m\cdot (v-x) = 1$, using any standard $\Sigma$-protocol for proving multiplicative relations between committed values.


Can the McEliece cryptosystem be used as an additively homomorphic encryption scheme?

In that case, what are the advantages of McEliece over Paillier encryption?

It's not that easy to think of any specific advantages; the public key will be huge (because you would need to expand the code to allow the relatively small initial error vectors to be secure), and those keys are already large enough to begin with.

About the only thing that springs to mind is the addition operation; for Pallier, the addition operation is addition modulo $\mathbb{Z}_n$, with the homomorphic McEliece, it would be addition in some field $GF(2^n)$, for some relatively large $n$, and perhaps some application would prefer that addition.

On the other hand, there are other cryptosystems (such as Goldwasser-Micali) which are homomorphic over addition in $GF(2)$, and running $n$ parallel copies would give you addition in $GF(2^n)$. It would appear likely that the homomorphic operation in McEliece is cheaper than the homomophic in $n$-ways parallel Goldwasser-Micali; however, to me, that sounds like a minor advantage (given the other disadvantages, such as Goldwasser-Micali has no bound on the number of homomorphic operations you can do before the ciphertext becomes undecryptable)


Simple RSA proof of correctness using Bézout's identity

Update: there is a serious gap in the reasoning after applying Bézout's identity, which concludes that there exists $d$ and $k$ with $ed+\phi(pq)k=1$. The fragment "where $d$ appears as the multiplicative inverse of $e$" attempts to link the $d$ thus exhibited to the $d$ used in RSA. But why would these $d$ share more than their name, especially since the $d$ and $k$ exhibited by Bézout's identity are not unique, and (at least the usual form of) Bézout's identity does not state a relation between these multiple solutions?

We want either a different statement of Bézout's identity, or getting rid of it altogether. That's easy: start from the definition of $d$ in RSA (whatever that is), and prove that a suitable $k$ must exist, using fact 3 below.

It is thought to prove that in RSA, decryption consistently reverses encryption. But hypothesis at time of starting this answer  where insufficient for that, as they did not insure that
$$\;p\ne q\;\text{ or }\;\gcd(m,pq)=1\;$$
This is required in RSA (illustration: try $p=q=5$, $\phi(pq)=20$, $e=3$, $d=7$; encryption of $m=10$ followed by decryption yields $0$ rather than $10$ ).

Now $p\ne q$ is made explicit, satisfying said requirement. But it is not apparent where this is used.

Not coincidentally, the proof still has a serious gap at the point where $1^k$ appears, which implicitly uses that  $m^{\phi(pq)}\equiv1\pmod{pq}$, because:

This proposition is wrong for some $m$, including $m=2q$ .
Fermat's little theorem is invoked as a justification, but an hypothesis in FLT is that the modulus is prime, while $pq$ is not.
FLT makes no mention of $\phi$ , and the definition of $\phi$ is not invoked in the proof.

Useful standard facts (for all variables in $\mathbb Z$ unless otherwise noted):

If $p$ and $q$ are coprime, then $pq$ divides $x$ if and only if both $p$ and $q$ divide $x$ .
If $p$ and $q$ are distinct primes, then $p$ and $q$ are coprime.
The definition of $u\equiv v\pmod w$ is that $w$ divide $v-u$ ; or equivalently that there exists $k$ such that $u+kw=v$.
For $w>0$, the definition of $u=v\bmod w$ used in RSA encryption and decryption is that $u\equiv v\pmod w$ and $0\le u<w$ .
FLT: if $p$ is prime, then $y^p\equiv y\pmod p$ .

That allows deriving the helpful:

if $p$ and $q$ are distinct primes, and both $p-1$ and $q-1$ divide $j-1$, and $j>1$, then $y^j\equiv y\pmod{pq}$ .

Proof hint: use fact 1 with $x=y^j-y$ , and other above facts.

Independently: it is used, but not stated, that the definition of RSA considered uses $d$ such that $ed\equiv1\pmod{\phi(pq)}$ . Another popular definition uses $ed\equiv1\pmod{\lambda(pq)}$ , where $\lambda$ is the Carmichael function. This definition is used in PKCS#1 and FIPS 186-4. It is mathematically satisfying, for it is necessary and sufficient, when $ed\equiv1\pmod{\phi(pq)}$ is merely sufficient.

Also, the proof would be clearer if it was restated:

$p$ and $q$ are primes;
the definition of $d$ used in RSA, and the definition of $\phi$ or $\lambda$ if they appear (in which case those are bound to be used in a correct proof!)
$N=pq$ ;
whatever hypothesis on $m$ (commonly, that is $0\le m<N$, with further restriction to $\gcd(m,N)=1$ if the condition $p\ne q$ is not used);
use of textbook RSA encryption $m\to c=m^e\bmod N$ ;
use of textbook RSA decryption $c\to m'=c^d\bmod N$ (with a distinct notation for the original message and deciphered messages);
what's to be demonstrated (this answer assumes that it is $m'=m$ for all $m$ satisfying the hypothesis made on $m$ ).

Also: there's a missing bit of reasoning, going from $m'\equiv m\pmod N$ to $m'=m$ .

Finally: textbook RSA is not a secure encryption algorithm (assume encryption of the name of someone in the class roll, which will be interrogated tomorrow; one can easily determine from the ciphertext and public key if that's her/him, or even who this is if the class roll is public).


public-key, H(public-key||pass) seems open to offline password guessing. Other than that seems to achieve what you want under the adversarial assumptions.


How to prove an encryption scheme is not CCA secure

Let $\Pi$ denote the encryption scheme you just described, and $\mathcal{A}$ be the adversary trying to attack this scheme.

Define the experiment $\mathsf{PrivK}^{\mathsf{cca}}_{\mathcal{A}, \Pi}$ as follows:

$\mathcal{A}$ has access to the encryption oracle $E_k(\cdot)$ and the decryption oracle $D_k(\cdot)$.
$\mathcal{A}$ outputs two messages $m_0$ and $m_1$.
A uniform bit $b$ is chosen, unknown to $\mathcal{A}$. $\mathcal{A}$ is given $c=E_k(m_b)$.
$\mathcal{A}$ is not allowed to query the decryption oracle on $c$. $\mathcal{A}$ however continues to have oracle access to both encryption and decryption.
$\mathcal{A}$ outputs bit $b'$. The result of the experiment is $1$, if $b=b'$, otherwise $0$.

So now, the scheme is considered CCA secure if the probability that the output of the above experiment is 1, is negligible. However, an adversary $\mathcal{A}$ could output $m_0=0^n, m_1=1^n$ and receive the challenge ciphertext $c=(r,s)$. It is not allowed to query $D_k(\cdot)$ on $c$. However, querying $D_k(c') = D_k((r, s \oplus 0^{n-1}||1))$ would return $0^{n-1}||1$ if $c=E_k(m_0)$, and $1^{n-1}||0$ if $c=E_k(m_1)$.

Depending on the result of the query, the output of $\mathcal{A}$ is equal to $b$ with probability 1.


How does the TLS cipher suite DHE-RSA-AES128-CCM8 work without hashing algorithm

These Cipher Suites are defined in RFC 6655 and use TLS v1.2's default: SHA-256.

To quote it from the RFC:

  These ciphersuites make use of the default TLS 1.2 Pseudorandom
  Function (PRF), which uses HMAC with the SHA-256 hash function.

The default-ness of SHA-256 is probably inferred from the following parapgraph from RFC 5246:

  In this section, we define one PRF, based on HMAC.  This PRF with the
  SHA-256 hash function is used for all cipher suites defined in this
  document and in TLS documents published prior to this document when
  TLS 1.2 is negotiated.  New cipher suites MUST explicitly specify a
  PRF and, in general, SHOULD use the TLS PRF with SHA-256 or a
  stronger standard hash function.


Original NTRU : How to calculate the size of private key?

Because the entries are ternaries, you can encode them using 2 bits, which gives an encoding of size $2 \cdot 107 \cdot 2 = 428$ bits.

There are smarter way to represent things though. But for general ternary strings you can't do any better than $2 \cdot 107 \cdot \log_2(3) = 339.18 $ (though it may be painful/costly to encode and decode to such a compact size.). Maybe one could also exploit the fact that we know exactly how many $1$'s and $-1$'s there are, which decrease entropy, but encoding/decoding becomes even more costly...


I work for Security Innovation, which owns the NTRU algorithms. Glad to see this interest!

You can look on this approach as two separate encryptions: one public-key encryption to transport $r_2$, and one symmetric encryption using $r_2$ as the key to encrypt $m$. This makes it look much more like standard practice in asymmetric crypto, where you typically use a public key crypto algorithm to agree a key and then use a symmetric algorithm to encrypt the data.

So the question is, is using $r_2*h + m$ a good symmetric encryption scheme? And the answer is no, it isn't really. For example:

It's not secure against chosen plaintext attacks. Consider an attacker who knows one of the messages 00000... and 11111... has been encrypted. She takes the ciphertext and multiplies by $h^{-1}$. If the result has the form of $r$, she knows the message was 00000... . If it doesn't, she knows the message was 11111... .
It's not authenticated. An attacker who knows I'm sending the message "pay \$200" can easily change it to "pay \$999".
It's not clear how best to encrypt multi-block messages. You can come up with ad hoc constructions such as CBC of course, but this would need to be defined.

You can address all of these problems, but at the cost of additional processing time. Probably, although the raw encryption mechanism is very fast, if you do it securely it won't be any faster than using a standard symmetric algorithm. So we would recommend just using NTRUEncrypt for key transport or for encrypting small messages, and if you have more data to encrypt, doing it with a strong symmetric algorithm.


Can you compress an elliptic curve private key in half?

This isn't the direction you were thinking of, however I believe that this is an answer to the question you meant to ask:

According to this, a $n$-bit key offers about $n/2$ bits of security. That got me wondering, can you compress the key in half?

One obvious approach would be to pick an $n/2$ bit secret $s$, and store that as your long term private key; then, when you're ready to start using it, you first compute $\text{SHAKE}(s, u)$ (where $u$ is some public identifier string [1]), and use the first $n$ bits of that as your private multiplier (which we'll call $t$, and so your public key is $tG$)
It would appear that the attacker has two possible approaches against this:

Brute force $s$; expected effort $O(2^{n/2})$

Use a discrete log algorithm to recover $t$ (which is just as good as $s$ to the attacker); expected effort $O(2^{n/2})$

It doesn't appear that there is a viable attack that combines these two; you can't tell if a potential multiplier is a possible value of $t$ without brute-forcing SHAKE; once you do that, you might as well stick with attack one.

[1]: We insert $u$ in the SHAKE call to try to avoid multi-key attacks (where an attacker is given a number of public keys, and tries to recover the private key for any one of them); it's analogous to the salt in password hashing.


What is the relationship between p (prime), n (order) and h (cofactor) of an elliptic curve?

The prime $p$ is chosen to make arithmetic in a choice of field $k$ efficient.  Typically $k = \mathbb F_p$ or $k = \mathbb F_{p^2}$.  Popular choices of $p$ are near powers of two, e.g. the Mersenne primes $2^{127} - 1$ used by FourQ and $2^{521} - 1$ used by E-521 and NIST P-521, or $2^{255} - 19$ used by Curve25519.  Other popular choices differ from a power of two by a small linear combination of of powers of two, e.g. $2^{224} - 2^{96} - 1$ used by NIST P-224 or $2^{448} - 2^{224} - 1$ used by Curve448.

The field $k$, the curve shape, and the parameters of the curve shape determine an elliptic curve $E/k$.  Every elliptic curve over a field of characteristic ${>}3$ has a representation in short Weierstrass form $y^2 = x^3 - a x + b$ for parameters $a, b \in k$.  Some curves also have representations in Montgomery form $B y^2 = x^3 + A x^2 + x$ or twisted Edwards form $a x^2 + y^2 = 1 + d x^2 y^2$.

The choice of curve shape affects performance and security properties of the curve, e.g. Montgomery curves have fast $x$-restricted scalar multiplication by the Montgomery ladder whereas the best single-coordinate ladder on curves that have no Montgomery form is the much slower Brier-Joye ladder.  The curve parameters often also affect performance, because, e.g., the Montgomery parameter $A$ figures into the Montgomery ladder as a multiplier, so smaller values of $A$ make the Montgomery ladder faster.

A field $k$ and curve $E/k$ determines a group of $k$-rational points $E(k)$.  These are loosely the points in $k$ satisfying the curve equation, and $\mathcal O$, an identity element.  (In more algebraic-geometric jargon, these are the points fixed by the coordinatewise action of the automorphism group of $\overline k$ that fixes $k$; that definition also works with projective coordinates, which are all-around much nicer to think about than affine coordinates.)  This is the group in which we do arithmetic, and define scalar multiplication of a point $P \in E(k)$ by $[u]P = P + \cdots + P$, the $u$-fold sum of $P$ with itself, with $[0]P = \mathcal{O}$.

The number of $k$-rational points $\#E(k)$ is an upper bound on the number of possible values we can get by scalar multiplication, and thus the maximum defense against ECDLP attacks: it is the maximum possible order of any element $P \in E(k)$.  So scalars are equivalent modulo $\#E(k)$: $[a]P = [b]P$ if $a \equiv b \pmod{\#E(k)}$.  The order of the field $k$ puts bounds on possible values of $\#E(k)$ by Hasse's theorem: $$|\#E(k) - (\#k + 1)| \leq 2\sqrt{\#k}.$$  So in order for $\#E(k)$ to be large enough to resist Pollard's rho, $\#k$ must be large too; for $k = \mathbb F_{p^e}$, $\#k = p^e$, and since $e$ is usually 1 or 2, $p$ must be large as well.  This is also why the high-order digits of the primes in the NIST curves may naively appear suspiciously the same as the high-order digits of the orders of the NIST curves.

We don't pick $\#E(k)$ in advance; rather, we pick $p$, a field, a curve shape, and curve parameters, and then compute $\#E(k)$ by Schoof's algorithm.  In order to resist small-subgroup attacks, we want $\#E(k)$ to be prime or nearly prime, so that $E(k)$ has at worst only negligibly small subgroups.  So we either randomly search the parameters to the curve, or find the smallest/fastest values, that make $\#E(k)$ the product of a large prime $n$ with a small cofactor $h = \#E(k)/n$.  Some curves are chosen with $h = 1$ so that $\#E(k) = n$ is itself prime; others are not, e.g. because every Montgomery curve has a cofactor $h > 1$.

Finally, we pick a base point or generator $G$ of prime order $n$.  This can also be done randomly or deterministically, e.g. picking the smallest nonnegative integer $x$ that is the $x$ coordinate of a point $G$ of order $n$, which we test by multiplying $[n]P$ and seeing if we get back $\mathcal O$.  The choice of which base point in an order-$n$ subgroup is immaterial, so there's no reason to even be tempted to choose this at random.

The attacker's job, which we hope to make hard, is to find a secret scalar $u$ given a multiple $[u]P$ of some point $P$ known to the attacker.  The legitimate user normally reveals $[u]G$ as their public key, so the subgroup generated by $G$ needs to have large order to resist Pollard's rho offline, and prime order to resist Pohlig–Hellman offline.

For ECDH, the legitimate user will also reveal $[u]P$ for an attacker-chosen $P$, which exposes them to Lim–Lee active small-subgroup attacks in which the attacker feeds in points $P$ in small subgroups where the ECDLP is easy.  If $\#E(k)$ is prime, then $n = \#E(k)$ and there are no nontrivial subgroups.  If $\#E(k) = h n$ is near prime, with, say, $h = 8$, then there are nontrivial subgroups, but the amount of information revealed by $[u]P$ is at most $\lceil\log_2 h\rceil$ bits—and sensible ECDH systems such as X25519 pick secret scalars $u \equiv 0 \pmod h$ so that $[u]P = \mathcal O$ for any point $P$ of low order, and the active attack reveals nothing.  (For more about choosing secret scalars for X25519 or Ed25519 or more exotic applications, see this answer.)

There is a host of other considerations you need to worry about, and they depend on what cryptosystem you're using: e.g., ECDH/EdDSA and pairing-based cryptography have completely different constraints.  You can find a reasonably comprehensive listing of criteria for curves safe for ECDH and EdDSA at SafeCurves, which also addresses twist security, completeness of addition laws, rigidity of selection process, and various other criteria for choosing curves.

Note that novel uses of curves sometimes require further criteria beyond SafeCurves, or careful handling beyond the standard DH or signature schemes.  For example, the cryptocurrency Monero was badly surprised by distinct but equivalent signatures enabled by the small subgroups implied by a cofactor $h > 1$.

For further references, and for some more detail about X25519 in particular, see an earlier answer I wrote.


In fact the equation is not used directly.

If you work in the field of integers modulo $p$, both the $x$ and $y$ coordinates are integers in the $0$ to $p-1$ range, so there are $p^2$ possible points. The equation tells you which points are part of the curve (the $(x,y)$ such that $y^2 = x^3 + ax + b$) and which points are not. In that sense, the equation defines the playground. The size of the curve (number of points which match the equation) is close to $p$, so the vast majority of possible points are not part of the curve.

However, if you just want to use the curve for adding points together, then the usual formulas (as seen e.g. here) do not use the curve equation: the $a$ parameter appears only in the formula for doubling, the $b$ parameter does not show up at all. The curve equation is used implicitly by virtue of the input points being part of the curve, i.e. fulfilling the equation.

So, in practice, the curve equation is used to verify that the input points are valid, i.e. part of the curve. When doing elliptic-curve Diffie-Hellman, each party sends to the other a curve point, as two coordinates $x$ and $y$. When receiving such values, you must first check that they define a point which is indeed a curve point, i.e. you compute both $y^2$ and $x^3 + ax + b$ to see if they match. If they don't, then the input points are not on the curve (or, rather, not on the curve you believe them to be), and bad things may occur.

As an optimization, the systems who do ECDH may send to each other only the $x$ coordinates. Indeed, when you receive $x$, you can compute $x^3 + ax + b$, which is equal to $y^2$. By computing the two (at most) square roots of that value, you recover $y$ and $-y$. In other words, from $x$ alone, you can use the curve equation to work out the (at most) two curve points which have that $x$ value. This is sufficient to do the ECDH. This is an optimization because it allows the two systems to send less bytes over the wire. This is called point compression and it directly uses the curve equation.


How is the zero-knowledge proof definition violated, here?

As with all signatures, an attacker who knows many $sig(sk,M)$ for different $M$ but the same $sk$ can learn about $sk$.

I guess you mean "can't learn anything about $sk$". Yes, that's right, but that's not the security definition of EUF-CMA (existential unforgability under chosen message attack). Informally speaking, it means that the attacker can not generate any valid signature on any message (excluding those he queried in the security game).

As you stated correctly, you can't simulate $P$: The existence of a simulator would be a direct contradction to the assumption that the signature is EUF-CMA: The simulator needs to be able to generate valid signatures with non-negligible probability without knowing the signing key, and in order for the signature to be EUF-CMA such a forgery must only be possible with negligible probability.

  However, it seems to fit the definition as I can't think of any argument as to why for any PPT attacker $A$ knowing only about $pk$ communicating with $P$, it's not possible to find a PPT $S$ only knowing about $pk$ which simulates the transcript between $A$ and $P$.

Yes, you can replace the verifier $V$ with a simulator, and this is actually zero-knowledge. However, this is quite trivial, if you look at your protocol: $V$ does not send any message in dependency of the secret value. It only does a DDH key exchange and then finishes the protocol by accepting the identity. In an exchange with an honest $P$ this will work out - it's more complicated if $P$ isn't considered to be honest (but that would also require the protocol to be different).

But what does it actually mean? Well, $V$ doesn't have a secret value. So there is no information kept secret. Zero knowledge does not mean, the other side doesn't learn anything - it means that the simulator can act like the party he replaced. And that's pretty much trivial if that party has no secret value.

But more importantly: This only states that $V$ doesn't send any information, which isn't in the protocol. It does not state anything about $P$ sending $sk$ in the protocol. For that you would have to replace $P$ with a simulator - which is impossible without breaking the security of the signature scheme, see above.

  Furthermore, I don't see how the transcript contains information about $sk$
  (which after all is what the zero-knowledge definition is about).

$sk$ is a secret value, so yes, a zero knowledge proof replacing $P$ with a simulator would prove that - if it existed. I think there is a misconception here: The main argument of the zero-knowledge proof is that you can create a valid transcript - but the corresponding party doesn't have the secret value. That means the transcript itself doesn't depend on the actual secret - the simulator doesn't know it. If you leave $P$ in and replace $V$ with the simulator, that doesn't change anything and you don't know if the transcript leaks $sk$ or not.

  .. is to give V information about pk without there being information about pk in the transcript.

The verification key $pk$ is public - you don't need to give that to $V$, he already has it.


Hash-based signature scheme XMSS/LMS susceptible to preimage/second preimage attack?

I'll first recall the security notions used for signatures and those used for hashes, and then try to answer your question.

The building blocks

For signature schemes, we try to have "existential unforgeability", where an adversary tries to forge the signature of a message that was not yet signed.
We also try to have the harder "strong unforgeability", where an adversary tries to propose another signature for a message that was already signed.

For hash functions, we have the notion of "first-preimage-resistance", also known as "being one-way", that is, it must be hard to retrieve a preimage.
Next we have "second-preimage-resistance", when it is hard to find a distinct preimage, knowing one existing preimage.
Finally we have the "collision-resistance", which is an harder property stating that it must be hard to find a pair of messages that hashes to the same value.

Now, LMS uses the Winternitz one-time signature (WOTS) as its one-time signature scheme (OTS), while XMSS is based on a variant of WOTS called WOTS+.

To XMSS' advantage, WOTS+ does not require its underlying hash function to be collision-resistant, so second-preimage resistance is enough.

Against classical adversaries it lessens the burden of birthday attacks, and is good for performance, because then smaller parameters will offer the same level of security.

LMS on the other-hand, being based on WOTS requires a collision-resistant hash function.

Now, if we can break the underlying hash functions, the proofs of security of signature schemes based on it would collapse with it, as mentioned by Poncho in this related answer. But this does not necessarily mean the signature scheme is completely broken in that case... (Even if it actually does in this specific case, see below.)

Quantum stuff

While we are at it, we should distinguish the Quantum world from the Classical one, because the "complexity" of the generic attacks against hash functions' properties will depend on the world we consider:

$$
\begin{array} {r|r|r|}
& \text{Classical} & \text{Quantum}\\
\hline
\text{Preimage} &  \Theta(2^{n})& \Theta(2^{n/2})\\
\text{Second-preimage} & \Theta(2^{n})& \Theta(2^{n/2}) \\
\text{Collision} &  \Theta(2^{n/2}) & \Theta(2^{n/2})\\
\end{array}
$$

This is so because Grover’s algorithm allows us to find preimages with a complexity of  $\Theta(2^{n/2})$ in a quantum world, however the birthday paradox bounds the complexity of the collision-resistance in the classical world already. (And we don't know a better way to go around it in the quantum world. See [Be09].)

So in a post-quantum world, it appears that WOTS based scheme are as good as WOTS+ based schemes. In the classical world, WOTS+ has a slight advantage...

The signature schemes

Let's now take a look at the signature scheme themselves, not their building blocks.

For both LMS and XMSS, a second preimage attack on their hash function would allow for a single forgery.

More importantly, a preimage attack would allow the attacker to derive his own Merkle tree from a public key, thus allowing him to sign as many messages as he wants. This being the consequence of the way the keypairs are created.

Finally, it is worth mentioning that Winternitz-based schemes are all vulnerable to two chosen messages attacks: if an adversary know the signatures of the all-0 and of the all-1 messages, then she can forge the signatures of all possible messages.
However, this does not compromise the asymptotic security of the schemes (see [BH16]) if we consider that we are signing message digests, since the all-zero message and the all-one message are no easily "found". (And other signature schemes are trivially insecure against the all zero message.)
But notice this can become a serious problem if we are considering "fault attacks" in our threat model. (Which can be the case with signature schemes.)

References

[Be09]   Bernstein, D. J. (2009). Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete. SHARCS, 9, 105.

[BH16]   Bruinderink, L. G., & Hülsing, A. (2017, August). “Oops, I did it again”–Security of One-Time Signatures under Two-Message Attacks. In International Conference on Selected Areas in Cryptography (pp. 299-322). Springer, Cham.


Does the discrete log assumption hold if k > p

Assume that you have chosen a large $k > p$, then one can show that $k'$ with

$$k = \ell \cdot (p-1)+ k' $$ can also be your equivalent key.

From Euler's Totient Theorem, we know that $$a^{\phi(n)} \equiv 1 \bmod n$$ for all $a$ relatively prime to $n$.

If your key $k> p-1$ then we can write it like below with division algorithm - division by $p-1$;

$$k = \ell\cdot (p-1)+ k' = \ell \cdot \phi(n)+ k'$$ Now place this into $a$'s power and use the Euler's Toitent Theorem:

$$a^k \equiv a^{\ell \cdot \phi(n)+ k'} \equiv a^{\ell \cdot \phi(n)} a^{k'} \equiv \underbrace{a^{(\phi(n))\ell}}_{\equiv 1 \bmod p} a^{k'} \equiv a^{k'} \bmod p$$

Therefore we have

$$a^{k'} \equiv a^k \bmod p$$ and by using $k$ you will not achieve any higher security, contrary you will calculate unnecessarily steps in modular powering.

If you want to achieve more security, you should use a larger modulus.


How would we design a fast circuit to solve LCS35?

Turns out the LCS35 problem was first solved on April 15, 2019 by Bernard Fabrot. It took 3.5 years of runtime on a single core of a standard modern CPU, using GMP.

Independently, the Cryptophage project solved LCS35 in less than 2 months, starting mid March 2019, using an FPGA-based system that performs modular squaring with extremely low latency.


Securely generating passwords based on a secret and a public identifier

What I did in one of my password generators is that given a secret key $K$, public data $\text{Pub}$, I first generate a solid "master key" $K_m$ via key-stretching the secret key using PBKDF2 (any other key derivation function would work, I just happened to have that lying around):

$$K_m = PBKDF2(K, \text{salt, iterations, } \cdots)$$

And then derive individual secrets via $HMAC(K_m, \text{Pub})$ (formatting the result as required).

It is pretty straightforward, and secure, but there are a few sticky points that you need to look out for:

If your public data $\text{Pub}$ is aggregated from multiple sources (say, an identifier string + time + counter + version + other metadata), you must ensure you do not end up generating duplicate $\text{Pub}$ data from different original inputs (or you'll get the same derived password back, of course). For instance, do not concatenate strings to create $\text{Pub}$. Instead, hash them all, and concatenate the hashes. Formally, the "input data $\to \text{Pub}$" mapping must be collision-free. In practice this easily gotten wrong.
Make sure all your security parameters are properly set up (number of PBKDF2 iterations, strong hash functions are being used, all that stuff)

The advantage of using HMAC like this instead of just using PBKDF2 and messing around with the salt is that:

It scales - multiple derived secrets can be efficiently computed via a single PBKDF2 invocation, whereas your method would involve invoking the key derivation function for each derived password (which may be very slow, if you use a lot of iterations)
It is actually using the underlying cryptographic primitives properly. A key derivation function is not meant to derive a lot of individual passwords from a given secret key by changing the salt. See this question for details. This is not the case for HMAC, which is, in fact, supposed to be used like this, as its main use is to generate fingerprints of arbitrary messages with a cryptographic key (and of course you don't need to change the key at each message) .Of course, you would probably be fine, but PBKDF2 is just not meant to be used that way.
It is less susceptible to misuse. Your method has no intermediate steps, only an input and an output. This makes it difficult to reason about security properties that each variable in your algorithm has, as well as any "cryptographic barriers" that your algorithm creates (e.g. "one cannot derive the secret key from a given generated password"). This is important because when you will need to add more features to your derivation process, you will need to redo the entire cryptographic analysis again to make sure you are not fundamentally breaking anything. In the approach I suggest, the intermediate "master key" has some known security properties (for instance, the secret key cannot be compromised by any manipulation done on the master key) which means I can easily tack on additional features without fear of introducing such and such security vulnerability. If you've ever heard the term "structured programming", this is pretty much an instance of it.

Speaking of adding more features, you will probably want a mechanism to verify that you typed in the secret key right (else you will get a garbage password out which won't match what you used before). It's not obvious how to do it using your method. However, with the improved algorithm, this is fairly straightforward - generate and store a random salt $S$ which you feed to PBKDF2 to generate $K_m$, and then store $Hash(K_m)$ somewhere, enabling you to verify if whoever is in charge of the secret key typed in correctly, without compromising it (or any derived password) if this stored information is somehow leaked (this is akin to storing the hash of the key inside the file when encrypting a file, to be able to tell the user if he typed the key in properly instead of complying and decrypting garbage).

Finally, once you have your final bytes, it's fairly easy to convert them to some charset that you can use as a password. The simplest way is to convert it to Base64, which is fairly convenient and efficient. Of course since they are just bits, you can convert them to whatever you want (hexadecimal, raw ascii, a pin number, etc..)


The birthday attack can be used with every hash function. It's a simple matter of probability (see: birthday problem). However, that only means that a hash function has to generate $2n$ of output to achieve $n$ bits of security.

It's fairly obvious that $H(m||k)$ is collision-resistant provided that $H$ itself is collision-resistant, since $H(m_1||k)=H(m_2||k)$ would imply that $H(x)=H(y)$ for $x=m_1||k$ and $y=m_2||k$.

However, the big advantage of HMAC over $H(m||k)$ is that collision-resistance of the underlying hashing function is not needed. Bellare proves in New Proofs for NMAC and HMAC: Security without Collision-Resistance that HMAC is secure as long as $H$ is a pseudorandom function, which is considerably weaker than collision-resistance.

Thus, even though the once popular hashing functions $MD5$ and $SHA$ are already broken, $HMAC_{MD5}$ and $HMAC_{SHA}$ are stil considered secure.


Is this a better GCM?  Not really.

You can derive an independent GHASH key for each message instead of using the same GHASH key for many messages as AES-GCM does.  It won't reduce security.  It's costlier without hardware support: you can't reuse the same GHASH lookup table to quickly leak secrets through timing side channelsauthenticate multiple messages.

But it's not much of an improvement in security: the difference is relevant only in the case that an adversary has already succeeded in forging a message and confirmed by the receiver that the forgery was successful (or the sender has reused a nonce, which works out to be just like the forger had made a forgery with the same nonce).

In this case, with AES-GCM, the adversary can forge arbitrarily many additional messages by recovering the GHASH key.
In contrast, with crypto_secretbox_xsalsa20poly1305, if the receiver demands sequential nonces or otherwise rejects repeated nonces, the forger can't use this to forge more than one message because the receiver will expect a different key for subsequent nonces.

It makes a difference only if the cost of a single forgery is small and you're really worried about how many forgeries you accept, which is not relevant to most applications—usually we consider a single forgery to be fatal, and strive to ensure it never happens.

This method is essentially what NaCl does in crypto_secretbox_xsalsa20poly1305: choose the Poly1305 key as the first 256 bits of the pad generated by the stream cipher XSalsa20, as suggested by Tanja Lange in 2006.  Exactly the issue you describe is addressed in the NaCl validation paper on p. 30, where Dan Bernstein points out the real security comes from bounding the forgery probability below $2^{-100}$.  This method is also by TLS with the TLS_*_WITH_CHACHA20_POLY1305_* cipher suites defined in RFC 7539 and RFC 7905, updated in RFC 8439 and included in TLS 1.3 in RFC 8446.  Of course, Salsa20, ChaCha, and Poly1305 also avoid leaking secrets by avoiding designs that present conflicts between speed and security in software implementations.  More on the background and shortcomings of AES-GCM.


Let's look at a picture of a generic feistel cipher

Notice that no keying material is used during or after that final swap. So, we can conclude that the final swap does not impact security at all.

So, why include it? It is so that all rounds will be identical. This could help with some implementations. That is all.


How to accurately calculate Unicity Distance for English?

A 16-bit cipher has $2^{16} = 65{,}536$ possible keys.  Thus, if you try to decrypt your ciphertext with every possible key, that's how many different (and essentially random) plaintexts you'll get.

Your calculation suggests that $\lceil2.46\rceil = 3$ bytes of ciphertext should be enough to uniquely identify the correct key, assuming that the plaintext ordinary is English text.  Such a short ciphertext would normally be characteristic of a stream cipher (or a block cipher in a streaming mode like CTR or OFB), in which case we can assume that each ciphertext decrypts to 3 bytes of plaintext (which, for an incorrect key, will be effectively random).

So let's test it.

I just wrote a simple program to generate 65,536 random 3-byte strings.  Out of those strings, all but 3,399 contained bytes outside the printable ASCII range, so I filtered those out.  Here are all the remaining ones:

F\G %EZ Cv> N}Q W&l LS} mM` "'8 Zi+ {KB '`j a6@ ;7O 3Hc }fH }&d W@L )]v 9Qy r1Y
ZG2 dc} `'x @4? WiC #7J T3' dq: s&. is_ laK Xr! fPi "MD LS4 (oz ELS 5${ ?6" E@,
PJ= S;C u|G :ap 1V~ ?Or g2V uE4 (O7 O3J bQ# a:0 k\: ~"" rWf eW4 Iqg bdT Oe) DYU
]n% A\V LzT s/N 1JO lZF *SQ p}/ YNY -V9 3f< r?g *Kp yyp E~Q <Jk r'w <^K c+_ w*w
iRt 8z, Fyf nq` K+. DuZ O<D 3co -Hz t?" !$S s`! ;wT }-M ZJI C9Z v8a *,D QcX 'cq
iM) $YX IDy K}9 Zmm J!y z[@ dXl $TC bR5 YDF 9/G $-p Pzu  Ff wpI {d" ~%# 'xw hpg
'[h E\7 Qsp ur# YN" TZm -}0 W(` T$r ~.J tKK ?~m \Y8 30] *P^ YlH g R # 4 nhs $ts
HS5 _i5 /2= al- w.t T+, ECg bU: Z}V w?6 #z  `R) ]n{ AiH jw> ;f1 (#Q  `S H_; a_O
n){ [Mt &"D xn  cr6 hJ~ HA2 ,gb ^/H 2M! &cZ }9K +wg Ivn {b{ ci= O7L %N, pac )|+
)n[ ivn td2 ^S} $Rf }[p %n% yWg F+V y-h F.6 36w D(A M-h Bea (yt Ka| w?b n)L z7W
8:d .l\ `|E f*" 8N% :_N $:p Z w K"l &hV Pr_ n/u $d- g   3L] g%y C|% S>P O[{ #IV
g"6 >tA Jp| Q={ jaM Q7U !#X pv" <JL t6= JIl %,` .K\ M,6 "MV kPH rMH ^T* .Hd jST
yX[ (~p GX} pSx S}?  @A }f_ Hy, ja1 cnp '5- zuy (\] u6w 2R% v([ QBK /jR ewr X)i
Z[: .F{ $]( {IS V4J ?01 K@+ 2VW |Ci -M* eb. oA8 1," h^s 2Dx V>F ndh 5VA `]  u(l
6R. -G~ s,b !Rd O]E [%o xBg wfd ;`^ L0' )<j y)M VO= /I* unB 3Ib VDi ~ok WBm BL-
u[9 1P6 @#d G=w %V/ YA> 'CT P}@ *E` *4H :$z /o$ w_J iBC lG| x}^ m7^ ]4v vz\ }-@
TE- XV{ ,6# p7G IvG tID 2g! >N^ x^" :^[ EG. 6a1 "D$ {YG QNS w}o +.f ~F- "kc i){
bq0 .I_ \gX 5wH .RQ 46U ]:+ sGx xOX 2<D ozM `|< k+: }$I ].B m%: Z1! K&^ k]] 4l2
`aW .q? 'K& zwp kcA O]p l@B (fg kJd v ^ k*> q:} q1f `_$ iz. ?b( O\H ~Cp )~' BMW
rnx \ms ]cy X!G Fs' zg1 px` 'v4 'V= jn1 ,"_ E+` ==, 2^T s77 <Ji "py uni 0~v 5lo
(Nd BL< ]V0 u"' r[= 6T\ oQW [pR cIN ~w5 |uT .&H QO8 itz g'E "Ea q}G h8" xH8 .%\
g^F Hh: #$b vg$ }+* #hz }TH v!T .~> 2=f QFs c;M 7SM "i| .3V VH4 {5Y ^b_ {q% w%/
QJ+ !u: m>> 7&g _`U Dwh 'OI :uC a!- !go f;1 3 m QqV !&. Xg> Dg` 71p UnJ 0Vc TLO
F\2 %(P w/G aJC SO8 ,k[ h#e 4r0 YG} PD2 |f^ #Q* ',L L-2 W"# ',n ukt ]`! qp! p6R
*`; il  Z!L uG+ S"" bJ$ kpX jRM kWM c4% z{8 0]! ^UK s^M ,$1 .TX +r! .D? U<+ Yr$
-i` 8-- .sg d&: zIZ sD| cVy :`U I"& n]u t;8 h4c lX} E P :9d J # LQX AdG VLP f8^
2rj hsg Slu o=G G"^ CEu %9) 'l4 i6P L$~ \jo hNl {l8 /RO 53V W}w .:O #Ov M'* 6yx
olv j[: XmZ Uus OUK hQN <mZ 0(& 6T5 _<e `w> $Ym F+> )!& j~8 _I* <t# VL~ L:M -t
:`r r9^ A<F 'L; z1g nzG :&= wp) KNk Z5f i)D @pC z-] m=  -j4 mN? qC) l5[ 31w ^,Q
1FZ w<T r!N R?} PaC edN Owa '^> }>; zju !XE ,h4 Ugx [=Y _vx "qf czs zM, M$e OW]
0o. X]` zT` /Fb k~} TVb z2B 0?c W{< *?g mpg llL .)8 ;1S '8j UO| ~a_ soU z+Q Q,e
L # ]Jn !jZ .,# M6{ Qyj m(| vPF  MY Z-5 :]^ Pt2 k[+ mYO W&D `"; <bF ]ZQ L?9 (-}
aE: yz1 9b) .pK t5= sDq eVx ?kL n*/ =B< (gl gv" lB/ ]o8 RQ6 r~_ DWN tY> q2Q 3-U
QeZ .Xx "]f B]3 xjS ]V9 E+c (Kp X.: wiD J9A m'Y _4j |}L SPL 3k, G4I zHn 3u6 `I'
Ka# D5. eaI 1p| t.Y ]"E zA; 81w Qzg !hK W@" FI( T7[ d9' Hp; BXa u@d &=[ b'8 'B&
:aF m.C zjs A)| Oxt ,so 37H 6VM P|/ /|U 9Q, lnn s%' |l0 {Xs q|F q ( 0)v p`z ):S
dZ. @;t ]Jn JVc .CD !+& #Vg %6Z VOl QoK ;z3 9A: m_X ",4 TQ  #}L  }J :O[ GPg $y<
|k: &f) (Ak Mx, N\L "bC 3}A +rL :<= .(I L?x D&] {Hr Np1 n*} 3n{ B<B Ub> edE F5@
I@_ Tv[ 4#9 j)J Na9 F}b 9T/ H#b .<Q WGC yQ+ ,oJ [Q% (rh 6C9 zw~ 9PS 0EG n$f o#
:.l 1!l 9}J b<2 fh% ^nb x<_ h9< DRO ed/ V>Y FlN 5zL 'H_ ssN pNL k'E |hR A~a ?98
s7G _4v a42 !zc zmg Bp| (A^ 6*_ rAv SES 'x= T*R <PY anf |pd #{g J%* ,2) <}? *1G
wi< T)q yq# +_z B'> s.> f|R GOY $Zo xEi M!a tHB 1Q  16* |im ./! 3W< zKl k+' q?o
&h- ^[" wu. O3I sU] 1.Q k+/ I*h -<; "V/ +R8 5&c ,>e 9p0 4zU NUG 2{b ity qz^ Y@0
q%] Kmj <@! $Cm wn| ?m] Ug} 'TE +{' Esj L<Y 7;t d39 ^Z3 R6J DCl ORt ME\ 3JU [Jh
TqK Ys  0{/ `ZN zOL fd% $'y |wp CJ] Y:L kp8 XV4 t+x n(g U`$ AcT eCJ fQX `3p n9R
[k; .;A c(c khd >P7 A~2 6xr ->_ $:Y |g% iwv ZC@ -'" Q"_ ("+ nGT 4px rAQ p,. \tb
Fyv QzQ >u? ]NM 'o@ 9N$ :lQ GwW OSN u_> Ixi ~Fs qB) 2C+ +IJ [X- ,)t  "Z <cV ',T
K>e Gl6 R[< y_" ?Q\ ;jL F`H ?mb `j7 f!M ~#Z BA7 ENP e'+ `Jx ]** HA> sJb Dh, na/
(~A K0Y 8>m X?t b'j }0I R!P og. c{V  if _Q( D/E Ph> v0  8Ui P/@ )3/ yhT lrk >*F
j]  vaL wRz xK& 0yk =+f |W! Q]L R7U Zqz 6iT  ?- " 7 v#8 /\~ gR` `+h C:, `;T jIo
IpB 0oz YH@ f&: ou^ Rp} k8@ rJZ yw- i|{ Jr{ %Ak 1,\ OLh P[n e&@ !.P GRY y?d /me
)od -xU f4= (X= :0S [Kj 5,V w`S KCA v2j VOC D#g &3t 'r7 bcW V'd p!r %E7 KG` e\5
c_Q vJ  Lym up" 2e% aC} :Sp "PO  br i1% jno W+G !~! [-2 {N$ M)r GPl 7|r :R^ 5f*
1i= Dew {?b )>g |8{ tA@ /Or _#Q #0Q %%G HN? |W[ *)] %fr InF QPJ k:> ]At y<. n>v
~6L ]z< qPt KJM tx> ;)} 5cF J\w 0z> y!M ahV (Js ^ow V[5 LuV {"4 o?) >[$ C@  Ri|
b{N r4s U92 E)s {!7 h)7 1t( Hp! /iM W$2 q"s tFx ?)5 '6u t_; f*D 2=~ &5k Ok7 9MY
cWO SHs dC> >6( @L- F57 t:& v0y X=j PG{ ?#[ {Lz aEO }~I \t! Z<+ lAy mHf 2AP ~:_
eb# [ko mO? 2|U ND1 8Wv @'0 |B$ OX} 6)q `z. H{& 7Y7 o2Q Vu. 2M# [NB &(W 39[ fb$
9u? L<w _G  l-Z 1Pt rGt Hnq ^y^ + $ 1R% q\W 8{Y aq5 4\] W\O 3Yc `c% x.P MV. +B/
y&0 @bZ Zu6 4d( \tX gUq #/] b30 XI[ |?3 #>2 qQC 'x4 (>' x.W %A< i/3  kd '~z |Dm
pc' S|P O[' u07 */1 zO{ />c %(N 7<X 8r8 <6e #(R GyR %}V l(6 /PA #/6 U#8 N+\ 6tS
sJ| {[e VK_ @[p bmV %[, q,% m4U IHQ 0O> *88 h36 !1, C"I zWU b-d -SL ?m! Uym CbI
8dm (|b [I, 6M5 3{L -T2 =?S =p8 /9; _)b  WC 9uQ 7h( zU% E*J #{0  e" OH1 BWf zQD
9}L I1? UTT hvU ,uB Y22 r;% K.j "}u 2Lt @)2 OOX !3e "E| *c8 )!9 6l* ,Cw -Lb h5V
/60 :!  5YP J*/ a/} {.7 2*4 po5 Ea$ hGd 8nH u"| Ls+ |*Z -he A_y /b* 2%> ]lv MC_
Cf| E8{ w,0 3@v kXp jrj !{! 3@E Buk 6&2 )J5 +~f fBO 4SD _F| yU" @uW V[Q T1@ ]Ax
YMg tcQ +|c nHG S!z (g> _*K W;M .AN }w$ hIQ @EG SeO fH; yZa uGx 5;^ >F_ eET `(?
!lH ;Gn ^Fn BWC MZf #!h vjj p'o /`i J*; #.F l`t |wf :U@ MO6 G`O j1/ \v+ ;!{ H]{
g'2 kc0 Y]u =aL g<0 (4z zMl !ov ]v: [p6 mr| 9TT g\= XVZ Hiz TAl +*f X2N kuS ^%M
^/M *|0 188 "cU eBH 6!| [|( *9g 0bu .M* o][ %m` ~9e exz   s sX6 JX" 8\R )}P /^K
U(` fwV 8wJ 45H 9QM /K) z%V j4v (^9 zRx j9y cI% mf^ JEa 1,[ J00 \_{ iSF Rj3 zn*
0C  0r: p k _]j 9<A =Xx \UD ^PR ^bV }YZ hXJ "S% Urk _y8 kwh GJ6 pr< gws [7" qvJ
pRB 1/| -U# $1^ uSJ l<; +mQ HJ| aMG TF\ `"' :Kt dR{ 3Zc LiU [CY bP1 GPX %|_ 0bH
l6? &+b dQ2 gFO Iw< RY% iVp A>g Fm( ;,J JEQ @<* p64 P}( +h_ V(4 +/? 7cQ GQ. 8{_
\s3 ?z9 ~aP B-2 <vg  lk h~v `:T #>m 9Sy iyc M8/ \Te g>\ ;.1 &c7 W_V VCZ x[0 66g
g3= cI{ R_, m3s &x$ Am' ==3 r)c NHG |)H !~O C4) L.> 7Kv bO< R!> DZ0 62o 'tO  ?%
g4o T_t @Zj tBi [,t u:V N}* qDX Wz< ;e> d$* X|F m?/ Xp( %0] uP5 (u2 qi! y`\ B[\
-{6 H]C 9:| (P5 EUu u)a (%+ N<B 5jF rL& 00e -'c I g !3  FCg I[R `%\ aGI 8Vy {oD
nTX F@t $RV ge5 E6e L!% V~  Qno =f' 5$m kgk  l7 %CB Z3T 2v` 5[" x`l 5@- dmx oXT
six EXh TK^ dz@ %mw zo] *@U 91F ?c) Oni OZ{ drv *EC 9l\ "=? 5;* kB3 ?&z W0'  G\
q%j Cr_ ysl ?_O bp: IXv A3) <Y% M w 0&Q &oT Gdp Hj{ lvd *h6 w,W z~X kZ& B]Q %/"
;IS t$[ m0* UHL ~U4 uA& anv w_[ ijW qcV >z| U;$ JY\ #:. }N~ Rm+ Z2~ L:y vCg 1)i
AH{ YG8 s'+ c}# P!W `e` Wr+ ^1K r!6 ao{ Q%P j<# }Q= {+- _8] \U` D@o I`+ i)R JJv
6?V z?? fx# Z+z smc H!y ]4< :J| u2T _dK lvU }I3 &j@ ;;4 c|A D87 ,y] K[@ |.f ,?I
VS0 .dk q4' "RW vZg gvP o*b \#. uX~ ~#: BUY X%S Kuv <"? kMP gWR @X` tNZ 1l~ "tc
ZMb @*+ )/u ;eI L|y ;RS XFR VP' Z}s ?y9 F$  kEK &Hn qoA a`d ht? \.w [w4 Bv[ w)w
oc  }fl lo$ vUk p3R `(h ")i `LB 3z$ go% Wvz A;9 !!Q L#G  Pj  CC 58c qhI |FL &L1
CmL -#t M@p gkb H?P b6: i`- XSC @:5 e]m )4Z u#b <}Z 7NB >i? {@Z k"f Qm2 $YM k9a
`z5 .%4 $6$  JT NPC D<; swH tkf j>) ;}e &jF l{o k&+ h&K ,RN ]I" 4vT CUR 'gb dV/
fFH ('v k_Y LfA 2y; RDV j)B Ces kX" #]T |S= 6`8 h'a @w^ TG$ [g$ 4#6 'r7 KQX Z6b
3$I MXQ /l  ph& -F6  0] :k. j?' US3 =S} |v3 (A1 iv> 2a= x%h a)K C@8 4H^ `Wq (2z
)30 y9- Cur [>/ [V/ -}Q `Bh Nti pHx ?d? */1 j0> ]i2 +9W yw" Glq w6Q ?R' &db E2`
]F. $sc 0?w }/& }:P =~M 1Dz |rg ]uk l`U UIg V73 a~% 3fd kul |P$ (#d j>~ mwS jJv
kfS %?| e`Z (B3 f[t =e} fg^ 0^) ju{ P'X cgW lJk Bb4 v%\  #/ D$c uJQ yb4 Q V TLq
^"G fK| bY) br7 (.^ 7Ep 380 Y9n u<  dFv ~pm J;. Te[ g#3 +k| 'Dx oPS Wu/ %@F 1k?
eGo Aw" -m/ 0)A t39 l&M ^*^ En" N`2 ~tG q[v nN/ %3!  H0 +w@ c\a m4T E,- \+* *0.
VA] Ma% "cc 9W# m{f 1Vg ^I$ w 0 nyY ]h= Wc9 (9l ./0 "69 =8z !?$ qB+ $>j |1g EUo
x!5 j8G 7IL d4% l`M gk= vh: F4o W)E >o! qaB x/n l79 RLV YVC +|c D"$ 95j ZCH dD2
foC }T& #di ]~j OP} bCs n'J D/t <!\ \#" hP0 n51 (Xz 5es K&o RM1 !41 ~U[ nw5 &h'
>Z| +Lo 0f| Fe~ jF^ kuu A~B ZVx `$' V0P J@2 L1C dn% w@b ^Tj KM< uyc Q7d XLc 6K%
c~" %Z5 R,5 /~= nm: fN6 %Zs 5u+ xQC M`W (@- a$[ Ns; |_B 911 Kqg %PZ 8}* |>+ \]6
%gc ~*i ATZ E[x !M3 >ia wZ! War >t2 HDE ~Pd ]@j 11C |!0 i|G [@P ek& Iu. LNf 3~P
UrY uTA v=P MRc Rz] Wf, =0| hv0 o[/ 00R X/{ cL] xTg eI. <L7 }QO DS5 yg! 2\} _?|
AX` ;=1 m p b~! 4"y ?4T GIZ 5*e @]@ *,~ 1lY {0A >tl #V&  yZ xSr hr& r2B %TH aw8
EwR EUr w+U c{W H1t X,5 KlB r<$ a*^ AJJ i]_ '}! g%i $4: H#5 c`K ?W3 L&E ^%' &?/
iYq 6=& $1r "0f 0c9 5W% W`o %9~ BA2 TIV 4zY n[# )ZL Md\ aPf {ll s8Y LiB rjw yd.
H<p Gqn u_q uS4 >sD /&\ ^4[ L{N !=p 3E! N27 n?u BJ] ,*g m"W %_> hzY Xcd /1@ ^o^
|mw p38 $z, Sp* fzJ G#> YD@ +Mq C}s 3Sk svY a~; BrN -Nu $3{ V2> ^-. b[E IFk ?zX
eal X^\ 1#= m/[ *SU $8l K[W <Ms "G< 3=J Ps# !^b H(k ~pJ )5L iHp -Ss #KW 93Q $KZ
Lbf mfa il^ rb& -LW Q)* -6\ .m_ ,Yl Xqp ?-s X@B `jl F-\ &(% G|J Wxe 0`G ho2 G.7
Gkb T!9 qD} ZX, T,@ MS8 >EK WM( x!I #Z\ `0R x5> R 1 5O) g?A m?z 9 % g]o F/F ^B{
=qa X[L |rA X>w 3'F H1t 7@A SfJ OC% #?o ob/ Sxm ;Ed ?\^ IOe GY1 a2_ OW) 4Q. aS~
yD+ s3q )(v EOU 37= !N& (=9 ]Nj qJ< t#^ JEB Om` 1X% ^4m rL, I:8 b1+ k,' D|t N{u
Bn3 !$K 6}Q T'9 `^B CBD Bk: q:1 ,Mh ] C (_N *j* I+\ _"? }IR -hF 3;? )*[ G6o Ktn
=G4 ~!S UR; Al, :3Y ]BP PJ0 8rc [k, 8p8 z\V u}- )cP Z@8 6{+ Zox "Pe ;E* Mj: "Oz
*c5 qL* gIa H~s z'] #dy mNT Asb "m* zw: XXP  H( Vyq ii6 $Vi AOZ "u; 7c+ M<G X7q
5dH T)v OX( +t  'ac G$4 4JZ VJ) kxI Xww ^.E sa$ c<j Qc. ! X u[2 m9$ D2u f7e -"f
:?V yex +AN ~3W h8n .m" @>i LM+ qAk Tq3 w$+ 0Pz g+T ed  e#' a1s 6P% jy~ (V/ p-f
q G 7.\ Zdl yxg DI' |Au pY1 K=# #xu y73 rv; bs) Eo} m/% <a0 P8O 0]p 4n> jRz Hys
Dlx k2* ePU X,{ u$o gIx O1@ [dH yjh 8Bj t@^ uD| AHd =CT rCQ Pu9 J@e C.Y z<k *2F
$`j ^&z J2, cKg g}' d?. t;8 9T\ 6jZ ;v] 8am @-0 2"/ /GE *6  EPK hUa *cb T=b p~F
O&\ 6{k LO" l9: 25e SKS CKC gC; X9+ N.3 I~% ^Qs ,C, D_@ )xx 'G) wl4 KGq 6:X l9^
~^_ <nH sp$ f-t | z @i0 q>7 017 Yge BF*  +g 2d^ 1lU /Zr q"i c,J 4ys /UB Mk3 NSn
Lbg %,/ *'6 2sS 3t= 7(t C[A 9.x V*m P?m {Z9 4"U }_[ -mT \0~ S%, uu( 5=D ,Z/ OI<
fS+ C^) H"< Ki= $^9 OJ% Tav *Fe ,p1 n0" #Lh {<9 O=b r\* O\) +[M ?^x @o; FKs Jd}
ARc r+P : [ .AW $DC D*C ~i[ {sY q\p niX sv0 5tC x!w g4L MS[ \`@ uuq H`4 K": G~z
|R} o;< cP% P@N T@J &Z; dNu xLx /eB BIH e%] Hzy {1< F\( {!' _{[ kZ$ o&@ yAU J4C
k6  E>/ k?] E!w g~g u!> N6d vw% hp_ c)' /'w }*t ]H- dT6 067 S(/ a?. i=: tH? ,TE
B}\ K M 2ao qfd ~`@ +D@ Oqx eHG Px^  QA k4f *mR 0T\ $Fp ;ph /XZ M(1 5*b :Fd 5R5
a9@ .[s wZy >@4 @?S Qd1 K*S P]Y \ [ &I8 / 1 2PF mD- :"\ e9s ,Q) neb |0M M&k OKB
znw {h< wmU '~G ;S_ ;td ~}B a<{ +kB 8tS 0eS *tq 52T Q.j [QB (4M xI/ ~k- Z9M ^(V
fG^ 7'K _M1 94# pLo 9&/ p/j _'/ [ 4 GIF ~pi \/; JAz "6X n,A :/` %B9 E&s CCm 6j5
l`' GjY ,LH b"q zU[ wta QH8 W"H v{e usF 3qd lUK $aE KpF ]qm },> MDD y(9 _4< ]E^
Sd/ Xs5 }GD b30 >>3 (z. PW\ TQ) I|} I6D {5+ ; f ESA ,s< \`" W?Q cp| 5Mv /f+ 0/R
:k@ Y:e "R[ *uz [9~ KiT b_% &)e "uY S,G /`O m]C Y^h k6G yxo 2"' tpU Y?$ )ig 5h&
@r| a]L >hL $=N fAo >R| D=} a\: ]HH rC^ 1<z a_> k#j lA- a6Y lXW <X/ >UM *q> y}e
$o# ]]h [Tj #`i wyF }we k_$ <'I bor @o% UsX 7RL &NT .&+ 9D# /P. RQg akK <u  kp(
44o 8dq 3U( up% ur6 ^NP 9I- soH 5j@ 3-O :|; }Wc =;{ ?ng =,u we8 y^t BYW 'p| "aA
Pc% "Av ?Hv K_g xY;  m< Y%% %LA r@~ O|R cvW &X> xuf "h  {pt &/p ,)- 16_ m6$ GlI
DG1 P&T zB/ k@w &j)  8u I-R pcd Xvg W@Y  CF quE .5& (KZ :iK  CX [p: $<; :Z/ h:_
u"2 <(" b|5 p>d !^T 7z4 O-5 ^rK 4_5 jO* +FF y;; \/R wbw &5&  N7 Gdu 4m= `L/ .">
>Bt g?Y t_% S}w fD' sL3 N&M Lh^ Bn, 1_c }{" 4B\ }Dq {Qz Mjc ,N' b82 }5" ^.j [)Q
~z4 g@S 6_^ FKS {HM ^%=  W] mIY $Q- *J" c'_ _UO lZg 4vB _dh H6  7S7 HCt C*S ov"
Lk9 pyO  "q 7'# cq( kGL 20Z L>l 9WU 9-W )I> <u\ (v* w1g u9& 8;[ Z'9 w4^ OMh J\R
Cy> qnu ,wm ':D *wt -+a AOo ,>W ,Ao =hs HfR B[Z s3% }nv I9u L0L krZ g-B &O3 `MQ
I(q JF8 w Y gK^ ?Vi q:1 3Um qUv JHn skb  bL MQL {=L ;t) iba {(U ?eE d'( Prz pB;
0]W M$+ [WU $8' wP= 0DU %1$ B9m 5sG _li vi5 qeY F8| 0K- P|C nts Hmi _`) pub HFQ
U:Z yDo "LI 33{ }dm l.f xh5 ^>+ j*W b.B D$o non !F, /&+ ")Q [dk w$* ~*& N8; y?G
H6S pg= /<O j_o ;ZR 1@D t=` l\i )'@ D]+ xCl "0^ =rZ sn^ @,P awQ x!q 6C2 ;mP @Xf
AM( <CR _2Q \AC 46> ge2 7L  tBs X*% h00 9'x QYr $Cl jG;  8y *<\ e?O n2J pmS [%7
!mW |3g 3T, t+% `kk %=@ W | Mo8 Oa2 ?!d dwY =JO mA{ s<l N=` L89 @Z? Leo p>| ,YK
w+H %8s r@\ @I*  Tj m(! &gs Q&= Hf% 37i D+9 %Q' |6U ?*  lJ2 Q18 94: 3(L S?X Afj
m*A Qz~ Hd9 Tqn )=8 s?m }2' J(% qs% %i! eus ,hP n?p `qE 2P~ d#p d6n {m{ mHv @:K
h>z Q?% wG" :f" Vsl fb7 p3A J[( {|j ..t @Qx L@Q ;'n S<\ 6c* Mtc YGj I<x zD? PCk
>a" -!g W8S vCg Hoj SkL }|* ZCn 3G0 $Ih 8s6 xpG {zI cpz :V) PFr yaX fA] #I| B5V
du2 JYi hx1 <`U 5E& p~h =mw 5E3 SRz ;+, 3zP rX7 0lX <[$ Om= #_! &-N %Hm >cN yMq
I6T NjU h{m XH6 M$]  94 ;Up NNq  :; Bh+ Na+ <v' $"e Y]5 @s/ Qq2 UyN 3r? YsL \ii
IAX :LY }[( m30 }kY y7v L/v 8XM =U= Sbo Vsf <pZ i\? y(a NLF fU` 'xQ eI< '*t 9TY
G3K cZ& :2X x[; ;|O YPE zxL !qK I=Y 1`u 4tx E4E *k* CI2 Y|P @gl ff& )c- cx1 (]u
b7y ump ?}a ]Fn o+O }vC Iak 1:~ \Q% /[+ tW\ ^QO >#3 Am^ EUX ife idb H%w =.d Hzg
9U9 cvd Exq kSF {ss Spd &Ce \(D ZTp 6kS l!9 2XF 0Z+ N:b *r1 qXb r}E <cS D*d  +N
y2? ,xO 1nx lC. xVj myv P(_ k[Z *8} ;HT jU] sPm lYu b%l ka^ 4R{ :n$ D=F \5{ Cyi
nu4 VnA WxE Zl) ACp ~,* VXm 4rG *!w 6<A yBW L*t `N7 b$k 0;I gfn ]:n @1D e^W hn$
Wps 9H4 Q89 8w8 JTu 045 9E9 puU \P6 >&P wR4 <pH ^MF M}, GJW S7* 62i Rd: hyt P\p
]DR Bzj t}Y Sw* _N| \1[ kQG UB  Wv: [Xh PT( zs8 %Qm !6_ ]*^ WnQ /3r n|h 9NC wpx
6}3 t34 EQp :ZJ r|8 Blx C?W XN< ~]B 7.z 0OK m". C>j N09 RIV iEs 2(r @m_ v"_ ,N_
/]V L$? ~?L UDE `W/ f8` J1u qnB 'F6 &wH hrO xmd WuD )Z8 n ( "6B 59^ T/m WH~ $te
nE0 yLG .vi tM, 6'< N;H PsW 1Kc [#j oPh t|2 ?]< sja 8yV <@; `f1 Kxh {nm -5E Ic/
78~ n8K Y@s q[z iJ[ q\i Z0? rL7 8>T BV: >i~ 9.9 %Dm Y\C Bo- Dz0 b=9 xd, w{N AJf
at9 0~c E<I 49l Z{s fk9 |\@ 2HG 2O" 3 m 7cm Gj5 EaB M9~ .\2 naK +F, /j& *7?

OK, that's a mess.  Let's filter those down to just the 560 ones that consist of just letters:

WiC laK fPi ELS rWf Iqg bdT DYU LzT lZF YNY yyp iRt Fyf DuZ ZJI QcX IDy Zmm dXl
YDF Pzu wpI hpg Qsp TZm tKK YlH nhs ECg AiH Ivn pac ivn yWg Bea jaM JIl kPH rMH
jST pSx cnp zuy QBK ewr ndh xBg wfd unB VDi WBm iBC IvG tID QNS sGx xOX ozM zwp
kcA kJd BMW rnx uni oQW cIN itz QFs Dwh QqV UnJ TLO aJC ukt kpX jRM kWM zIZ cVy
LQX AdG VLP hsg Slu CEu hNl olv XmZ Uus OUK hQN nzG KNk PaC edN Owa zju Ugx czs
TVb mpg llL soU Qyj vPF mYO sDq eVx DWN QeZ xjS wiD SPL zHn eaI Qzg BXa zjs Oxt
lnn JVc VOl QoK GPg edE WGC DRO FlN ssN pNL zmg rAv SES anf GOY xEi tHB zKl NUG
ity Kmj Esj DCl ORt TqK zOL AcT eCJ fQX khd iwv nGT rAQ Fyv QzQ GwW OSN Ixi ENP
sJb yhT lrk vaL wRz Zqz jIo IpB rJZ OLh GRY KCA VOC bcW Lym jno GPl Dew InF QPJ
qPt KJM ahV LuV tFx cWO SHs aEO lAy mHf rGt Hnq gUq qQC GyR bmV IHQ zWU Uym CbI
BWf zQD UTT hvU OOX hGd kXp jrj Buk fBO YMg tcQ nHG hIQ SeO yZa uGx eET BWC MZf
vjj zMl XVZ Hiz TAl kuS eBH exz fwV zRx JEa iSF hXJ Urk kwh gws qvJ pRB uSJ aMG
LiU GPX gFO iVp JEQ iyc VCZ NHG tBi qDX EUu FCg aGI nTX Qno kgk dmx oXT six EXh
Oni drv ysl IXv Gdp lvd UHL anv ijW qcV vCg JJv smc lvU vZg gvP BUY Kuv kMP gWR
tNZ ZMb XFR kEK qoA vUk Wvz qhI CmL gkb XSC NPC swH tkf CUR fFH LfA RDV Ces KQX
MXQ Cur Nti pHx Glq UIg kul mwS jJv kfS cgW lJk uJQ TLq dFv oPS eGo nyY EUo qaB
RLV YVC ZCH foC bCs kuu ZVx uyc XLc xQC Kqg ATZ War HDE LNf UrY uTA MRc xTg GIZ
xSr EwR EUr KlB AJJ iYq TIV aPf LiB rjw Gqn hzY Xcd fzJ svY BrN IFk eal iHp Lbf
mfa Xqp Wxe Gkb SfJ Sxm IOe EOU JEB CBD Ktn Zox gIa mNT Asb XXP Vyq AOZ kxI Xww
yex qAk Zdl yxg jRz Hys Dlx ePU gIx yjh AHd rCQ cKg EPK hUa SKS CKC KGq Yge NSn
Lbg Tav FKs ARc niX uuq dNu xLx BIH Hzy yAU qfd Oqx eHG wZy neb OKB znw wmU pLo
GIF JAz CCm GjY wta usF lUK KpF MDD ESA KiT yxo tpU fAo lXW wyF bor UsX RQg akK
soH BYW cvW xuf GlI pcd Xvg quE wbw Gdu Mjc FKS mIY lZg HCt pyO kGL OMh qnu AOo
HfR krZ qUv JHn skb MQL iba Prz qeY nts Hmi pub HFQ yDo non xCl awQ tBs QYr pmS
dwY Leo Afj Tqn eus mHv Vsl Mtc YGj PCk vCg Hoj SkL ZCn xpG cpz PFr yaX JYi SRz
yMq NjU NNq UyN YsL IAX Sbo Vsf NLF YPE zxL ump Iak EUX ife idb Hzg cvd Exq kSF
Spd ZTp qXb xVj myv sPm lYu Cyi VnA WxE ACp VXm yBW gfn Wps JTu puU GJW hyt Bzj
kQG WnQ wpx EQp Blx RIV iEs UDE qnB hrO xmd WuD yLG PsW oPh sja Kxh AJf EaB naK

Do any of those strings look like a plausible beginning for an English plaintext?  Well, actually, a few do — just at a glance, I see Bea, Dew, War, Cur, six, anv, pac, RIV, CUR, BUY, etc.  I'm sure there are plenty more that might be extended into a meaningful message, even if it's also clear that the overwhelming majority of three-byte strings are not meaningful English.

OK, but according to our unicity distance estimate, there shouldn't have been any reasonably English-like strings in the sample, or at least not more than one or two.  So what went wrong?

Well, the main mistake we made is that the estimate of 1.5 bits of entropy per character is an average for long texts, and measures the entropy per character conditioned on the preceding text — that is, loosely speaking, it says that, given a piece of English text randomly truncated in the middle, you have about a $2^{-1.5} \approx 35\%$ chance of correctly guessing the next character after the break in the text.

However, the first character at the beginning of the message (or at the beginning of the fragment we're looking at) is much harder to guess, and thus carries a lot more entropy — I would guess somewhere around 4 bits, plus one bit for capitalization, if it's not known.  The second character is also likely to be harder to guess than usual, due to the limited amount of context available, so let's randomly allocate it 3 bits, including the possibility that the capitalization might (or might not) change.  (We could calculate more accurate entropy values from a suitable text corpus, but I don't happen to have one handy, so let's just go with these guesstimates.)

This leaves us only $8-5=3$ bits of redundancy for the first byte, and $8-3=5$ bits for the second one.  Assuming that the following bytes have approximately the $8-1.5=6.5$ bits of redundancy assumed earlier, that means that, to uniquely determine a 16-bit key, we need $2 + \frac{16-3-5}{6.5} = 3.23$ bytes, which rounds up to $4$, not $3$.

So let's try the experiment again, this time with 4-byte strings.  For brevity, I'll only show the 133 strings that contain only letters and spaces:

mDJP Ptwu wZIC fXRU OPht rmHg yXp  ffhC IqJl wocL mHxY jUqM reta XzRi EVRY IhIy
FtIB JZYV PhFP OpVy wrWe eoJf XwAN XtcF Bhmj Ipgx abFz MDCg ImqN ehbl Iafe zjfM
DaiH jaKu gQBF qkbi EoIo JzIb IAOT BhFI wYqZ uecv rHhy oKFP INHF WuQA GCmI InIO
YaHR lieX KfQw NzvY qPsn E Xn Xfxa AHyy OZFg qZFE FQsx ffje THPs djhU MFap xRqt
Pkwb cvsU UhfV frvF rfNN eiNt UxTt tTiV duLt MzPC rXUU YSOi vkxk URZj kzYZ RUNB
ZpyD UVpn ysFw temX IkcN UAaR sGDH HKhr YvXo QDSc KUr  YLCv cIjU MvOa eXWi Cqmg
Phed OTnf gbuV aJgL dVH  pabP l wz xNEF oVIv DWzL aUza dqMm ZQEh BcVZ vBTg nGsd
WcGs hUFW Vvrh qcEg RLhi NOuI vKkP KPsT rECZ yaKJ oSnU hkiO CKZN evJH BVJg vlVN
sYrM iXfM LoWf TxOv GNkP

At a glance, the only one of those strings that looks like a plausible start of an English word (let alone a message) is reta.  EVRY and RUNB get close, but if we're going to allow such misspellings or run-on words (which, of course, a practical cryptanalyst should), then we really ought to increase our per-character entropy estimate to account for that.

In fact, one false positive is about what we should expect on average, if our sample length was reasonably close to the unicity distance.  (This is true by definition, since the unicity distance is defined as the length of ciphertext needed to make the probability of a random incorrect key decrypting the ciphertext to a valid plaintext equal to one per the number of keys.)  To reduce the expected number of false positives to a negligible value (say, 0.0001), we really ought to take a look at a couple more characters yet, and see if they still look like English.


How are the functions used in cryptographic hash functions chosen?

The functions considered are binary functions of 3 bits to 1 bit (extended to bit vectors, that is bitwise functions). There are $2^{(2^3)}=256$ such functions.

All the functions considered are balanced; that is, there is an equal number of input combinations for which the function outputs 0 and for which the function outputs 1. That reduces the number of functions to $8!/(4!)^2=70$.

Aggregating balanced functions identical within the $3!=6$ orders and the $2^3=8$ polarities of the $3$ inputs leaves only $6$ classes (see final section); keeping the lexicographically first function in each class:

    z   y   x           g0      g1      g2      g3      g4      g5
    0   0   0           0       0       0       0       0       0
    0   0   1           0       0       0       0       0       1
    0   1   0           0       0       0       0       1       1
    0   1   1           0       1       1       1       1       0
    1   0   0           1       0       1       1       1       1
    1   0   1           1       1       0       1       1       0
    1   1   0           1       1       1       1       0       0
    1   1   1           1       1       1       0       0       1

Of these, it is excluded g0 and g4 since at least one of their input has no influence on the output. The other four functions exhibit properties that tend to be good for diffusion:

for any of their input fixed to either polarity, the output is non-constant when we vary the other inputs;
any of their input influences the output for at least two of the four combinations of the other inputs.

These surviving functions are:

g1 Majority, used for $f_3$ of SHA-1 and $f_2$ of SHA-2 (which turn out to be identical)
g2 Choice, used for $f_1$ and $f_2$ of MD5, $f_1$ of SHA-1, $f_1$ of SHA-2; this function is also called Select, or Digital Multiplexer (input x being 1 or 0 chooses which of y or z is the output);
g3, used (within order and inversion of inputs) for $f_4$ of MD5; as noted in comment, that function $(x\wedge y)\oplus z$ is also the Toffoli gate's third output;
g5 Parity, used for $f_3$ of MD5, $f_2$ and $f_4$ of SHA-1.

Addition per comment: g1 and g2 additionally have the property that any of their input influences the output for at most three of the four combinations of the other inputs; or, in other words, are not fully linear w.r.t. any of their input. This is desirable in some sense, as too much linearity opens to some differential attacks. This might be why g1 and g2 are preferred to g3 and g5 in SHA-2.

A comment asks for the derivation of classes of balanced functions of 3 bits to 1 identical within order and polarity of inputs. We'll represent a function by an 8-bit value $b_{000}\,b_{001}\,b_{010}\,b_{011}\,b_{100}\,b_{101}\,b_{110}\,b_{111}$ giving the output $b_{zyx}$ for the 8 combinations of the 3 inputs $z\,y\,x$.

Balanced functions have $b_{000}+b_{001}+b_{010}+b_{011}+b_{100}+b_{101}+b_{110}+b_{111}=4$. We scan them in lexicographic order (equivalently, numerical order when using big-endian convention); if not excluded, that's the function representative of a new class, and we exclude the functions obtainable from that by permutation of inputs, or changing the polarity of inputs. We can do this by considering any of the 6 following transformations applied, or not (there's some redundancy in applying the 64 combinations and many functions are excluded multiple times, but it does not harm):

turning output to $b_{000}\,b_{010}\,b_{001}\,b_{011}\,b_{100}\,b_{110}\,b_{101}\,b_{111}$ (exchanging $x$ and $y$)
turning output to $b_{000}\,b_{001}\,b_{100}\,b_{101}\,b_{010}\,b_{011}\,b_{110}\,b_{111}$ (exchanging $y$ and $z$)
turning output to $b_{000}\,b_{100}\,b_{010}\,b_{110}\,b_{001}\,b_{101}\,b_{011}\,b_{111}$ (exchanging $z$ and $x$)
turning output to $b_{001}\,b_{000}\,b_{011}\,b_{010}\,b_{101}\,b_{100}\,b_{111}\,b_{110}$ (complementing $x$)
turning output to $b_{010}\,b_{011}\,b_{000}\,b_{001}\,b_{110}\,b_{111}\,b_{100}\,b_{101}$ (complementing $y$)
turning output to $b_{100}\,b_{101}\,b_{110}\,b_{111}\,b_{000}\,b_{001}\,b_{010}\,b_{011}$ (complementing $z$)

We first get 00001111 = g0, and exclude 00110011, 01010101, 10101010, 11001100, 11110000; then get 00010111 = g1, and exclude 00101011, 01001101, 01110001, 10001110, 10110010, 11010100, 11101000; and so on. In the end, there are only 6 classes.


Is direct RSA encryption of AES keys secure?

This scheme suffers from a classic problem of textbook RSA which is mitigated e.g. by RSA-KEM (as outlined by kelalaka) or RSA-OAEP.

When you compute $k^3\bmod N$, you'll experience that $$c=k^3\stackrel{k< 2^{256}}{\leq}\left(2^{256}\right)^3=2^{768}\ll 2^{2000}<N$$

Now remember how $x\bmod N$ works: If $x\geq N$, then you recursively compute and return $(x-N)\bmod N$ and else you return $x$.

Given that $c\bmod N$ fits the "else" case, $c$ is simply returned. Now an adversary can just compute $\sqrt[3]c$ as your calculator does for real numbers (with a bit more precision), you get $k$ back.

Note that the above weakness doesn't violate the RSA assumption because the assumption explicitly states that $x$ is uniformly randomly sampled from $\mathbb Z^*_N$ 1 in $c=x^e\bmod N$.

1: $\mathbb Z^*_N$ is the set $\{1,\ldots, N-1\}$ without any $x$ such that $\gcd$$(x,N)>1$


Is the private key of a private/public key pair also a symmetric key?

In a local discussion someone said the private key (of a private/public key pair) would also be a symmetric key.

Well, not quite.  If we're talking about public key encryption (there are other flavors of public key cryptography), what is correct is that "what has been encrypted with the public key can be decrypted with the private key".

What this means is that to encrypt, you need the "public key".  That is, unless the private key had enough information for you to deduce the public key, you couldn't actually encrypt, and so it wouldn't work as a symmetric key.

Now, practically speaking, in most public key cryptosystems, the private key does have enough information to deduce the public key. However there is at least one example were it doesn't; large exponent RSA; where both exponents $e$ and $d$ are chosen to be large (and you don't insert the CRT parameters into the private key). With this system, given $N$ and $d$ (which is all the private key has), you cannot efficiently recover $e$ (and hence cannot encrypt, even though you can decrypt).

Of course, a public/private key pair, when considered as a unit, will work as a key in a symmetric system.  We do run into the practical issues that it is a hideously bad symmetric system (as any public key cryptosystem is slow and has huge ciphertext expansion, compared to any realistic symmetric cryptosystem), but it would work.

As a side note: if your document states:

  I found places that document "what has been encrypted using one key of the private/public key pair can only be decrypted with the other key of the pair."

Then either the document had context that stated that it was specifically talking about RSA, or it was written by someone who doesn't know what they're talking about.  Most public key cryptosystems cannot be described this way; they do not provide any way that allows talking about 'decryption' (recovering the original message) with the public key.  RSA can be described as a 'trap door' permutation (if you ignore padding, which in practice you can't), and so could many multivariate signature schemes (although those are mildly obscure); hardly anything else can be.


A block cipher whose key changes after each block

In general you want to treat primitives like block ciphers as black boxes. You first analyze and try to break the block cipher. Once it is proven to operate correctly you can use it as primitive for a block cipher mode of operation. The mode of operation can then be proven to be secure assuming that the block cipher primitive operates well.

If you don't treat the block cipher as a black box then you will basically have to show that the mode of operation doesn't invalidate the security analysis of the block cipher.

The subkey derivation may not be the most important part of a cipher, but that doesn't mean that there aren't many things to consider.

It seems that tweakable block ciphers do indeed provide an answer to what you want to achieve (see the answer of pg1989 and the comment of SEJPM).

Lets quote the paper that introduced them:

  Block ciphers (pseudorandom permutations) are inherently deterministic: every encryption of a given message with a given key will be the same. Many modes
  of operation and other applications using block ciphers have nonetheless a requirement for “essentially different” instances of the block cipher in order to
  prevent attacks that operate by, say, permuting blocks of the input. Attempts to
  resolve the conflict between keeping the same key for efficiency and yet achieving
  variability often results in a design that uses a fixed key, but which attempts
  to achieve variability by manipulating the input before encryption, the output
  after encryption, or both. Such designs seem inelegant—they are attempting to
  solve a problem with a primitive (a basic block cipher) that is not well suited
  for the problem at hand. Better to rethink what primitives are really wanted for
  such a problem.

That's from the introduction of the paper Moses Liskov, Ronald L. Rivest, and David Wagner: Tweakable Block Ciphers.


How to distributively compute a secret of that form $\mathsf{s=sk\cdot g^a}$?

I assume that your question relates to sharing a secret specifically of this form. Furthermore, you want to guarantee this even if the dealer is not trusted and may try to share a secret of a different form. Otherwise, you could just use any secret sharing (or verifiable secret sharing) scheme.

However, note that $s$ as you wrote actually does not have any special form. Specifically, since $a$ is uniformly random, $sk\cdot g^a$ is just a uniformly random element in $\mathbb{Z}_p$. Thus, as you have worded your question, you can use any secret sharing scheme for which the domain of the secret is $\mathbb{Z}_p$.


One gap in your proposed argument is that $ctr$ is known to the adversary (it is included in the ciphertext), whereas saying "$G_k(ctr)$ is pseudorandom" implicitly assumes that both $k$ and $ctr$ are kept secret.  This is a minor point, because $G_k(ctr)$ is pseudorandom even if the adversary is also given $ctr$.

A more serious gap is that to prove CPA security, you must deal with the fact that the adversary can obtain multiple ciphertexts for messages of its choice.  If, for example, $ctr$ was always the all-zeros string (which would preserve the pseudorandomness of $G_k(ctr)$), the scheme would definitely not be CPA secure, because it would be breakable by a "two-time pad" attack.  So a correct proof must deal with the possibility that $ctr$ might be repeated from one message to the next, or more generally, that $ctr+i=ctr'+j$ for some two initial counter values $ctr, ctr'$ and offsets $i,j$ for two ciphertexts.  This issue is what most of the Katz-Lindell proof is dedicated to addressing, and is the source of the "birthday term" $q^2/2^n$ in the analysis.


Name for a Ceasar Cipher that uses random offsets?

In short, it is a stream cipher.

The security of the random number generator is crucial in this design. Also, the key exchange ( the seed transfer) is not defined. To be good use Diffie-Hellman Key exchange and use a KDF to derive the seed.

Modern design is AES in CTR mode where the CTR mode of operation turns a block cipher into a stream cipher and that doesn't require padding. The better use the AES-GCM that provides Confidentiality, Integrity, and Authentication. Another one is ChaCha stream cipher and in Authenticated mode it is ChaCha20-Poly1305.


$(a)-$ Let $p$ be prime. Then $\sqrt{p}<A<\sqrt{p}+1 $, so $0<A^2-p<2\sqrt{p}+1$. This means that, prime divisor of $A^2-p$ is less than $3\sqrt{p}$.

Now try to solve $(b)$ for next $10$ points.


Is regular CTR mode vulnerable to any attacks?

Summing up the discussion in the comments: What you are describing is the CTR Mode of operation of block ciphers, which requires an encryption function ("E" in your diagram) like AES. So, "should I use CTR or AES?" should instead be "should I use AES with CTR or with another mode?"

As @RickyDemers already mentioned, CTR mode (without any additional authentication step) is malleable, which means that it is possible to change the meaning of the ciphertext. For example: you want to encrypt the message $m=01010101$. Counter mode will use the counter and the encryption function to generate a keystream, for example $s=10010110$, and compute the ciphertext

$$c = m \oplus s = 01010101 \oplus 10010110 = 11000011$$

An attacker could now, for example, flip the second bit in the plaintext $m$ by changing $c$ to $c'$:

$$c' = c \oplus 01000000 = 10000011$$

The decryption would use CTR mode to derive the same key stream $s$ as before, but use it to decrypt $c'$, which would result in

$$m' = c' \oplus s = 10000011 \oplus 10010110 = 00010101$$

As you can see, the second bit (which used to be $1$) was changed to $0$ by this change, while leaving the remaining parts of the file data unchanged. This is called malleability.

You can prevent this by using a message authentication system like HMAC or, even better, an authenticated encryption mode like GCM, which functions like CTR mode but also authenticates the data and thereby makes it impossible to change the ciphertext without being detected. Many systems were broken because they did not use any authentication of the ciphertext, and more were broken because they did the authentication wrong.

So, my reply would be:

Use AES with a sensible mode: XTS or EME if you want to authenticate your data separately using HMAC or something similar, or GCM if you want to do it all at once (I'm not sure if GCM is suitable for full disk encryption though, and be careful when using it, there are some ways to shoot yourself in the foot)
Also, if this is to be more than an experiment on your part, seriously consider using an established disk encryption tool instead
Use a cryptographic library instead of writing the encryption code yourself. There are many non-obvious ways to shoot yourself in the foot, and any one of them may be fatal to the security of your system. Established cryptographic libraries have been vetted for these bugs and while they do crop up occasionally, they are much less likely than in any code a single person can write.
Read and understand this question and all answers in its entirety.
Your misconception about AES and CTR mode indicates that you are pretty new to the field of cryptography. That's fine, everyone was a novice at some point! But make sure to understand the field a little more before building anything serious, because bugs in cryptography are both hard to find and can be devastating if they occur in software used in practise.


Do you need to reuse the key for multiple messages without any way to distinguish the role of each message, e.g. by a message sequence number, or file position for a collection of records in a single file?

If you have some short identifier that is never reused between each role, or if you need encrypt only a single message with each key, then you can pick your favorite stream cipher, say ChaCha or AES-CTR, with the message role (sequence number, file position, etc.) as the nonce, and just chop the first 30 bits off the stream.

If you must reuse the key for many messages with no way to distinguish the role of each message, then you need format-preserving encryption.


A question about verifier in zero knowledge proof

The meaning of this has two aspects:

After running the protocol successfully, the verifier is convinced (with overwhelming probability) that the information is genuine.
The verifier can by no means extract the information from the protocol. It is simply impossible (not unlikely, actually impossible).

Very simplified a zero knowledge protocol goes like this:

First, the prover sends some information to the verifier
Then the verifier generates a random value (often just a single bit) and sends that to the prover
The prover answers based on that random value, and the verifier can check that answer combined with the first value and his random value.

The protocol is set up such a way, that only if the prover truly knows the secret information, he can send the correct answer in the last step with certainty. Otherwise he has to rely on luck. So if the verifier used random values in the second step and the prover didn't know them in the first step, there is a certain chance (often probability $0.5$) that the verification in the end does not work out.

And lastly, the above steps are done multiple times and only if the prover passed all of them the verifier is convinced. With probability $1/2$ per round, the remaining uncertainty after $k$ rounds is $\frac{1}{2^k}$.


Prevent communication with a node assuming full transparency

This sounds like a job for…public-key signature!

Store a public key on the node, and reject any incoming message if it does not have a valid signature under that public key.

If you're concerned about performance, verification under RSA with $e = 3$, or Rabin–Williams, is very fast.


Turn a password into a key without using salt

For passwords with sufficient entropy you can use a KBKDF - a key based key derivation function - that allows a non-constant sized input and performs entropy extraction. The extraction of entropy into an intermediate form of a specific size is made explicit in HKDF by a function called HKDF-extract.

  HKDF follows the "extract-then-expand" paradigm, where the KDF
     logically consists of two modules.  The first stage takes the input
     keying material and "extracts" from it a fixed-length pseudorandom
     key K.  The second stage "expands" the key K into several additional
     pseudorandom keys (the output of the KDF).

  In many applications, the input keying material is not necessarily
     distributed uniformly, and the attacker may have some partial
     knowledge about it (for example, a Diffie-Hellman value computed by a
     key exchange protocol) or even partial control of it (as in some
     entropy-gathering applications).  Thus, the goal of the "extract"
     stage is to "concentrate" the possibly dispersed entropy of the input
     keying material into a short, but cryptographically strong,
     pseudorandom key.  In some applications, the input may already be a
     good pseudorandom key; in these cases, the "extract" stage is not
     necessary, and the "expand" part can be used alone.

Keys can then be derived from that intermediate state by HKDF-expand, which allows additional input parameters such as in the info field that may - for instance - include a label identifying the key to receive the output keying material.

Usually the extraction phase is implicit - not explicitly identified; this is for instance the case for other KDF's that rely on hash functions.

In others the extraction is not present; this is for instance the case for many KDF's that rely on block ciphers. Those start off with a symmetric key, which needs to conform to the requirements of symmetric keys that already presume "concentrated" entropy.

HKDF does not require a salt. It does take a salt as parameter but it may be empty. HKDF is significantly strengthened by a salt though, see chapter 3.1 for more information on when / how to apply a salt with HKDF.

The discussion about these principles for HKDF is applicable to many KDF's that may be equally secure within the protocols where they are used. The good thing of HKDF is that the principles are explicitly named and therefore - hopefully - well argued & applied.


How to implement "online" feature of GCM?

As you suspect, it's possible to rearrange the GHASH computation so that can compute both the AAD and the encrypted data online and independently.

As you recall, GHASH is defined as:

$$\mathrm{GHASH}( \{a_{i-1}, a_{i-2}, ..., a_0 \}, \{ p_{j-1}, p_{j-2}, ..., p_0 \} ) = \\ a_{i-1} H^{i+j+1} + a_{i-2} H^{i+j} + ... + a_0 H^{j+2} + \\p_{j-1} H^{j+1} + p_{j-2} H^{j-1} + ... + p_0 H^2 + C H$$

where $\{a_{i-1}, a_{i-2}, ..., a_0 \}$ is the AAD, and $\{ p_{j-1}, p_{j-2}, ..., p_0 \}$ is the plaintext, and $C$ is a block containing the lengths of the AAD and the plaintext.

We can rearrange this into:

$$(a_{i-1} H^{i-1} + a_{i-2} H^{i-2} + ... + a_0 H^{0}) \cdot H^{j+2} + \\(p_{j-1} H^{j-1} + p_{j-2} H^{j-2} + ... + p_0 H^0) \cdot H^2 + CH$$

We can online compute $\Sigma a_i H^i$ and $\Sigma p_i H^i$, and so you are iteratively computing $\Sigma p_i H^i$, you also compute $H^{j+2}$.  Once we have those collected, compute:

$$\mathrm{GHASH} = (\Sigma a_i H^i) H^{j+2} + (\Sigma p_i H^i) H^2 + CH$$


What if we increase the key length of DES and use ECB Mode, then will we get the different output as ECB mode encrypt with the same key?

Increasing DES's key size (by using 3DES instead) won't mitigate at all the weaknesses of ECB mode. That's because the block size in unchanged, and the same identical blocks in plaintext will remain identical blocks in the ciphertext. See Wikipedia's illustration for what that can imply for raw bitmap images.

To some small degree, using a block cipher with a larger block size, such as AES, will give some level of mitigation (e.g. when enciphering a raw bitmap image, it will be less recognizable). But that's very partial (doubling the image's resolution will more than offset the mitigation).


is it safe to leak some information about scrypt result?

That should be fine, as long as you never reuse it for any other purpose.  (E.g., if you want to encrypt another file with the same password, generate a fresh salt.)

But there's a simpler approach: Use AES256-CTR with nonce 0 and forget about AES256-CBC altogether.  No more worry about unaligned message lengths or padding, how to choose initialization vectors, etc.

I encourage you to consider authentication too.  For example, instead of the unauthenticated AES256-CBC, you could use AES256-GCM, or AES256-CTR with HMAC-SHA256 in encrypt-then-MAC composition.  In fact, maybe you would be better off just using the scrypt(1) utility, which has a simple format.


Let $N$ be the block size in bits, used in the Merkle–Damgård construction of the given hash function.

The smaller $N$ is, the more iterations have to be executed to yield the hash value, hence the algorithm becomes more (computationally) expensive.

The larger $N$ is, the more inefficient it becomes for messages of length $M$, where $M<N$, since the input message would have to be padded out until it fills at least one block of size $N$. It would not be desirable having to add 1013 bits of data if you only need to hash 10-bit inputs. (in fact, you would have to pad out a bit less since there is a field-length field at the end of the block)

Finding a trade-off lies with the developers - I guess 512-bit blocks have been established as a consensus as MD5, and most SHA-2 members work on this length.


Why do PKI schemes need security proofs?

If you cannot provide even a basic proof of security, or a reduction of the protocol security to the underlying algorithms in use, you should assume the protocol is insecure.

Even with a security proof, a logical analysis of attacks against the protocol should be performed, as a proof may be limited to security against a limited amount of attacks, and in practice all attacks must be considered, even those that are uncommon or even impractical.


The answer from owlstead and its comments covers WEP part quite nicely.

This answer concentrates on CTR and OFB.

Strictly speaking, CBC, CFB, CTR, and OFB modes always use IV or counter. I'm assuming that the question was more like is it possible to use CTR or OFB mode securely without transmitting IV. I.e. for instance, start at all zeroes IV/counter and increment the counter for each message. This appears to be possible and secure. (As long as you're careful enough to never reuse same counter+key combination.)

Details for selecting IV for CTR and OFB modes

The answer for IV(/nonce in CTR and OFB modes is found in document NIST SP 800-38A: Recommendation for Block Cipher Modes of Operation, which describes these modes. This document tells in Appendixes B and C various recommendations by NIST for choosing IV/counter for CBC, CFB, CTR and OFB. Long story short,
for CTR and OFB modes, it is sufficient that IV/counter used is always unique for the same key, as long as it is also unique for each invocation of the encryption operation.

In other words, counter is ok for CTR and OFB. In OFB mode, it is not safe to use cipher text from a previous operation as IV, a practice that has been often used with e.g. CBC mode. The language of NIST specification may be misleading. There is evaluation of cipher modes of operation from Rogaway, which you may find easier to read and understand, and containing a lot of additional detail.


If you look at RFC 4122 then you can see which bits are not random. I think that are 128 bits in the UUID and 6 of them are non-random to indicate the scheme used. That leaves 122 bits of UUID, which is probably enough to consider them relatively random. Only if you generate many millions of them is there a chance of collision. However, there is a reason why a hash commonly has an output size of double the wanted security level because of the birthday paradox. And 122 / 2 = 61 bits of security, which is on the low side. So it might be a good idea to extend at least the randomness of the value.

Of course you can always add random bits to them and a MAC using a secret key would that. It would allow you to reject tries with relative confidence. Furthermore, you could reject those before a database lookup. How much confidence depends on the security of the MAC, usually limited by the output size of the MAC. It does of course require the additional burden of key management though.

Alternatively you could simply add more random bits to the UUID or to generate a proprietary 256 bit UUID. However, I think the MAC scheme over the UUID is relatively elegant as the MAC can be over the UUID, while keeping the UUID scheme intact, and it can be extended by adding a salt. Of course the secret key must be kept secret otherwise an adversary can generate the same.

The disadvantage is that the UUID as send with MAC and possible salt is not standardized anymore, so you have to think about an alternative canonical encoding of UUID and MAC.


Number of terms in Balanced boolean functions?

In general, if the algebraic normal form representation has few terms, an implementation can be faster.But such a simple representation can also lead to certain attacks.

You can represent such an Sbox as a mapping from $GF(2^4)$ to itself as well as a univariate polynomial mapping from $GF(2)^4$ to itself and what's sparse or simple in one representation can be complex in the other.

There are criteria such as resilience to consider as well, which may be the reason about your comment on nonlinear order.

Saarinen has a nice paper on classifying 4x4 Sboxes here.