If what you have is a machine that computes RSAES-OAEP and not a machine that computes $x \mapsto x^e \bmod n$, you don't really have the tools to do RSA-KEM.  You're better off doing what you were doing in the first place—unless I can talk you out of going near the incoherent minefield of hysterical raisins without meaningful guidance that is the WebCrypto API.

Now, it is technically possible to abuse RSAES-OAEP to give the simulacrum of an RSA-KEM implementation.  It might even be compatible with RSA-KEM implementations on either side, but you really shouldn't try to simulate RSA-KEM using RSAES-OAEP unless you are desperate and your RSAES-OAEP machine accepts the OAEP randomization as a parameter and returns it on decryption and you have a separate subroutine to compute OAEP alone without the RSA part.

For a message $m$ to an RSA modulus $n$, the sender could do:

Pick $k_0 \in \{0,1\}^{256}$ and $r \in \{0,1\}^{256}$ uniformly at random.
Compute $x = \operatorname{OAEP}_n(k_0, r)$.  (This is the padded element of $\mathbb Z/n\mathbb Z$ before we compute modular exponentiation, raising it to the power of the public exponent $e$.)
Compute $k = H(x)$ (e.g., use HKDF).
Compute $y = \operatorname{RSAES-OAEP}_n(k_0, r)$ so that $y = x^3 \bmod n$.
Yield the key $k$ and its encapsulation $y$.

On receipt of $y$, the recipient could do:

Compute $(k_0, r) = \operatorname{RSAES-OAEP}_n^{-1}(y)$ or reject if RSAES-OAEP decryption fails.  (Beware padding oracle attacks!)
Compute $x = \operatorname{OAEP}_n(k_0, r)$.
Compute and yield the key $k = H(x)$.

Note that this also requires a subroutine to compute OAEP itself, and requires the public key operation $\operatorname{RSAES-OAEP}_n$ to accept the OAEP randomization $r$ as a parameter alongside the short string to be encrypted, and requires the private key operation $\operatorname{RSAES-OAEP}_n^{-1}$ to yield the OAEP randomization $r$ that was encrypted alongside the short string.

So in the end, although as a black box this is probably (unless I made a mistake) indistinguishable from RSA-KEM, it's much more complicated to implement than just encapsulating the randomly generated key $k_0$ with RSAES-OAEP as a sort of ‘RSAES-OAEP-KEM’ as you were doing in the first place.


If $E_{k_1}(p_1) = c_1$, what is the probability that there exists key $k_2$ such that $E_{k_2}(p_1) = c_1$?

DES is a block cipher with $b=64$-bit block width, and $w=56$-bit key width (ignoring key parity bits). An ideal model of a block cipher is that each key defines an independent, random-like permutation of the blocks. Under that model, if $E_{k_1}(p_1)=c_1$, then

For each key $k\ne k_1$ there is independent probability $u_1=2^{-b}=2^{-64}$ that $E_k(p_1)=c_1$
Hence for each key $k\ne k_1$ there is independent probability $v_1=1-u_1=1-2^{-b}=1-2^{-64}$ that $E_k(p_1)\ne c_1$
There are $n=2^b-1=2^{56}-1$ keys $k\ne k_1$, hence the probability $v$ that for each of these keys $E_k(p_1)\ne c_1$ is: $v={v_1}^n={(1-u_1)}^n=(1-2^{-64})^{(2^{56}-1)}$
Hence the desired probability $u$ that there exist any key $k\ne k_1$ such that $E_k(p_1)=c_1$ is: $u=1-v=1-{(1-u_1)}^n=1-(1-2^{-b})^{(2^w-1)}=1-(1-2^{-64})^{(2^{56}-1)}$
For integer $n>0$ and real $\epsilon$, it holds that $(1-\epsilon)^n=1-n\,\epsilon+O((n\,\epsilon)^2)$
Therefore, for $m\gg1$ and $m\,|\epsilon|\ll1$, it holds that $1-(1-\epsilon)^{(m-1)}\approx m\,\epsilon$
Applying the approximation in (6) to the expression in (4), with $\epsilon=u_1=2^{-b}=2^{-64}$ and $m=2^w=2^{56}$, it comes
$$u\approx2^{w-b}=2^{-8}\approx0.39\%$$

Note per Ilmari Karonen's comment: the approximations made after step (4) fail when the key width $w$ approaches or exceeds the block size $b$, as would be the case for 3DES ($b=64$ and $w\in\{112,168\}$) or AES ($b=128$ and $w\in\{128,192,256\}$). We then want a better approximation. We can use ${v_1}^n=\exp(n\log(v_1))$ and $\log(1-\epsilon)=-\epsilon+O(\epsilon^2)$, giving at step (7) $u\approx1-\exp(-2^{w-b})$, valid for $b\ge20$ and $w\ge20$. That's mathematically more accurate, but numerical accuracy requires extended precision when $b-w$ is positive and sizable, which is dangerously close to hold for $b-w=8$ in the question.

Note: Our model of DES is imperfect, in particular when we consider many plaintexts $p$ : DES has additional properties that our model misses. In particular the complementation property $E_\overline k(\overline p)=\overline{E_k(p)}$; that the permutation of blocks for any particular key is even; existence of weak keys. More generally, DES is a particular block cipher (a Feistel cipher within a few cryptographically neutral bit permutations). But given that in the context there is as single plaintext $p_1$ considered, and that DES is a fair cipher (except for its last-century key and block size), it is reasonable to believe that our model is good enough for an excellent approximation of $u$ for random choice of $k_1$ and $c_1$.

Note: with DES a fixed cipher, we can no longer talk of the desired probability $u$ when the whole of both $k_1$ and $c_1$ is fixed. I conjecture that the approximation still holds when $c_1$ and all but say 16 bits of $k_1$ is fixed, but wonder what happens when $k_1$ is fixed to some particular values (like all-zero, which is a weak key).


Hardness of Short Interger Solution in lattices

No, we cannot say that Short Integer Solution ($SIS$) problem is NP-Complete.

The results from those two papers are not directly related like that, because on the first one, the reduction is from $SIVP_\sqrt{n}$ to $SIS$ while in the second paper, $SIVP_c$ is proven to be NP-Hard for any constant $c$.

Until now, there is no proof that $SIVP_\sqrt{n}$ is NP-Hard and, since it has been proven to be in the intersection of NP and coNP, researchers believe that it is not NP-Hard.


Is that possible to calculate modular inverse of a point on elliptic curves?

No, this is a known variation of the computational Diffie-Hellman problem, called Inverse computational Diffie-Hellman (InvCDH), according to which on input $g$, $g^{x}$, it is difficult to find $g^{x^{-1}}$.

See section 2.2 at Variations of Diffie-Hellman Problem by Bao et al. for more info and problem reduction proofs.


Zero-knowledge transfer of value protocol inspired by EC El Gamal

As is, there is nothing to prevent Alice from spending more than she holds by letting her $a$ underflow modulo the order $n=2^{256}-\mathtt{14551231950b75fc4402da1732fc9bebf_h}$ of $g$.

Update: and as pointed by VincBreaker in that answer, as is there is nothing to prevent Bob from computing Alice's commitment of transfer of $\bar c$ from Alice to Bob: the only use of Alice's private key is to compute $s$ that she shares with Bob, and with that $s$ Bob can do anything Alice can. A fix is considered in said answer.

Whether the above properties are a functional issue or not depends on the application, but these are something to watch for electronic money.

As proposed, the padding scheme for 64-bit value/amount $\bar x$ (with restriction to $0\le\bar x\le2^{64}-2$) is $x=P(\bar x,r)=\bar x\,2^{192}+r$ for $k=192$-bit uniform $r$, and $\bar x=Q(x)=\displaystyle\left\lfloor\frac x{2^{192}}\right\rfloor$ used to extract value/amount $\bar x$ from $x$, with $Q(P(\bar x))=\bar x$. It follows that if $a=b+c$ then either $\bar a=\bar b+\bar c$ or $\bar a+1=\bar b+\bar c$ hold, with next to equal odds. Whether this is a functional issue or not depends on the application (but see last section for a workaround).

Another security issue is that for $k$-bit random padding $r$ there is at best $k/2$-bit security against someone trying to confirm a guess, for example of a transaction amount $\bar c$ from $C_1=c*G=\bar c\,2^{192}*G+r*G$, by solving for $k$-bit $r$ the equation $r*G=C_1-\bar c\,2^{192}*G$ using e.g. the Baby-Step/Giant-Step algorithm. Same for values held $\bar a$ and $\bar b$.

Thus I'd say that 256-bit ECC is too little, especially if we want exact balance as follows.

If the uncertainty of one unit is an issue, we can improve on that with a sacrifice of some bits of $r$. That could be $k=176$-bit uniform $r$ with $P(\bar x,r)=\bar x\,2^{192}+r-2^{175}$ and $Q(x)=\displaystyle\left\lfloor\frac{x+2^{191}}{2^{192}}\right\rfloor$. In this way most transactions are exact, including the first $2^{16}$ with certainty, and in practice likely the first $2^{22}$.


As your message treated as one element in the finite field defined by $p$, it must be smaller than this $p$.

There are other reasons, but you mention one about why to use hybrid systems. When you encrypt using public key, the process starts by generate a random symmetric key used to encrypt your data. What is encrypted using the public key is this symmetric key.

Another reason is to encrypt to more than one recipient. The data itself is encrypted once for all, and is this symmetric key the one encrypted for each target.

Note that the size of a symmetric key is much smaller than the size of its equivalent in security in public key.


Difference between symmetric and asymmetric hash function?

It is probably not the case of your example, but in some sense "asymmetric hash functions" do exists: they are called trapdoor hash functions (or also chameleon hash functions).

Very briefly, they are collision resistant only if you don't know their trapdoor secret key.
Such functions take 2 arguments (instead of the usual one), and the second argument is used as randomness.

So, without the trapdoor secret key it is infeasible to find 2 "messages" $m_1,m_2$ and 2 randomness values $r_1,r_2$ such that $H(m_1,r_1)=H(m_2,r_2)$; while, with the trapdoor key, you can efficiently compute (for any given triple $m_1,m_2,r_1$) a value $r_2$ such that $H(m_1,r_1)=H(m_2,r_2)$.

Hope this is clear enough. If you want, you can also see this  article by Shamir and Tauman or this one by Krawczyk and T Rabin


DES generating the same ciphertext for different plaintexts and identical key

No, that is impossible. The reason is simple: How would you decrypt this? If you input the ciphertext and the key into the decryption function, than you have to get exactly one output, not two. How would you decide which output is the correct one?

The DES encryption and decryption functions are bijective under one given key. This means that for every possible input there is exactly one output. Not more, not less. Every output has only one matching input, not more, not less. You can reverse any transformation made, forward and backward, at least if you have the key. This behavior is assured by the inner Feistel network of DES.

All this has to be the case for every possible key, even weak or semi-weak ones.

This is the case for every "standard" block cipher: DES, AES, Blowfish, Twofish, MARS, Serpent, RC5, RC6, ... They all meet this requirement. Different operating modes can change this, through. Different plaintexts can lead to the same ciphertext with different IVs, for example for CBC. I don't think that the question focuses at this, but I want to include it after reading Maarten Bodewes - owlstead's answer.


ANSI X9.31: the purpose of the date/time vector in the PRNG?

From ANSI X9.31:1988, Appendix A.2.4 (Generating Pseudo Random Numbers Using the DEA):

"Let DT be a date/time vector which is updated on each iteration."

The purpose of $dt$ is to supply a value that is different each time the algorithm is seeded, so as to generates a different sequence, even if $V_*$ (the initial value of $V_{old}$) is a fixed secret.

The algorithm seems to be secure even if $dt$ is known, and predictable, e.g. a 64-bit counter starting from 0; at least, that's the design goal. However it must not be possible to return $dt$ to an earlier value. In other words, $dt$ needs to be a "number used once", sometime called nonce.

Beware that an adversary could set the clock, hence $dt$. In the absence of a specific mechanism, that might allow her to re-generate a previous sequence!

It is probably best if the adversary can not choose $dt$ (and that makes it much easier to insure that $dt$ is unique).


How is multiplication inverted in IDEA's decryption round?

The multiplication operation is indeed not uniquely reversible given just the output. But we also have one of the inputs, namely, the subkey. We can use that to reverse the multiplication.

Decryption for IDEA requires changing the subkeys in the key schedule. I didn't find a good description of IDEA online, so I went back to Applied Cryptography, 2nd Edition, which had a good description (as well as the provided diagram):

  Decryption is exactly the same, except that the subkeys are reversed and slightly different. The decryption subkeys are either the additive or multiplicative inverses of the encryption subkeys. (For the purposes of IDEA, the all-zero sub-block is considered to represent $2^{16} = –1$ for multiplication modulo $2^{16} + 1$; thus the multiplicative inverse of 0 is 0.)

For decryption you would take the result of the original multiplication operation and multiply that by the multiplicative inverse of the subkey that was used. (The subkey was derived from the original key, and the multiplicative inverse of a subkey can be calculated from the subkey.) This yields the original input value.

This works mathematically because the multiplication operation is performed modulo $2^{16}+1$ which (combined with with the provided special case treatment of 0) forms a mathematical group structure. Within a group, every multiplication operation is guaranteed to have an inverse value that can be used to reverse the operation.

It forms a group because, in general, the numbers $1, 2, ..., p-1$ form a multiplicative group modulo a prime $p$ (this group can denoted by $\mathbb{Z}^*_p$), and in our case $2^{16}+1$ is prime. The special case for 0 is necessary because of a minor implementation complication: A variable value of $0$ isn't in the group and $2^{16}$ can't be stored in a 16-bit variable. This was easy to resolve: Define the unused $0$ to represent $2^{16}$.


Why SHA-512/256 when we already have SHA-384?

The truncated versions of SHA2 are introduced in 2005 and in the Cryptographic hash Workshop, in 2005, Kelsey listed the reasons as;

Interoperability and security reasons
Need drop-in replacement for SHA1 (MD5)
Have unbroken hashes of wrong size

ECDSA/DSA key sizes
File and protocol formats

Though not mentioned by Kelsey or any other NIST document, the truncation also helps to mitigate from the length extension attack of the SHA series that is due to the Merkle-Damgård construction's architecture problem.
Using different IV enables the domain separation that enables us to have two different random oracles *. It makes sure that the truncated versions have different results. With the domain separation  $$\operatorname{SHA-224}(m) \neq \operatorname{SHA-256}(m)|_{224}$$ where $|_{224}$ is the truncation

What's the point of having 2 of them

If you have an already implementation that uses SHA-256 and you want to mitigate from the length extension attack then SHA512/256 is a good choice. Also, it possibly may increase attack strength.

Also, when you need only 256 but hash output, if you use the SHA512/384 you need to trim that yourself. Not a good idea in the case of programming and in the case of security since you are using the same random oracle.

The ECDSA/DSA key sizes: ECDSA-384 signing SHA512/384 is a good choice especially for 64-bit devices since SHA512 is designed for 64-bit.

Someone tried to use SHA512 and has problems with TLS 1.2. if you are adopting ECDSA-384 signing SHA512/384 is a good choice as above.

For SHA512/224 and simply for 224-bit usage is due to the Triple-DES security, $112 \cdot 2 = 224$. There is a very extensive answer for this by Fgrieu SHA-224 Purpose.

*A random oracle is like a kind of hash function and the same concept applies to hash functions.


Searchable Symmetric Encryption VS Deterministic encryption?

Comparision is not possible between Searchable Symmetric Encryption (SSE) and Deterministic Encryption (DE). The reason is given below:

DE is an encryption scheme with the property that it always generates the same ciphertext for the same message. Hence, this is more prone to Guessing Attacks.
Examples of DE are Unpadded RSA, AES with ECB mode, and Order Preserving Encryption etc.

SSE is Crypto paradigm that facilitates searching over the encrypted data. You can use DE as an encryption scheme in SSE for encrypting the data and then make it searchable with the help of searchable indexes. However, the output of this SSE could be more prone to Guessing Attacks because DE was used in SSE.


Really simple RSA style public private key generator

A simple example would be:
$e=3\;$ which is the lowest usable public exponent in RSA, and will simplify encryption
$p=23\;$ a prime such that $\gcd(p-1,e)=1$
$q=41\;$ a prime other than $p$ such that $\gcd(q-1,e)=1\;$ and
          also such that $e^2\bmod\operatorname{lcm}(p-1,q-1)\ne1$
$n=943=p\cdot q$
$d=147=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)\;$ or $d=587=e^{-1}\bmod((p-1)\cdot(q-1))$.

Encryption of a message with symbols restricted to !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ and perhaps control characters such as LF, using public key $(n,e)=(943,3)$ is, for each symbol in the message:

convert the symbol to an integer less than 91 by using its ASCII code; for example, A would give $65$.
right-pad a random digit in range [0…9], yielding an integer $m$ less than 910, thus less than $n$; for example A giving $65$ and the random digit $7$ would yield $m=657$.
compute $c=m^3\bmod943=m^e\bmod n$ which can be done with a 9-digits calculator and a single final modular reduction (or by hand; in that case, or using an 8-digits calculator, we want to compute $m_2=m^2\bmod n\;$ then $c=m_2\cdot m\bmod n\;$); for example $m=657$ would yield $c=288$.
output ciphertext block $c$ as 3 decimal digits, with leading zeroe(s) if necessary.

Decryption using private key $(n,d)=(943,147)$ is more tedious, because it involves computing $c^{147}\bmod943=c^d\bmod n$. It can be done by left to right scanning of the binary expression of the exponent $147=10010011_b$, thus computing $c_2=c^2\bmod n\;$, $c_4={c_2}^2\bmod n\;$, $c_8={c_4}^2\bmod n\;$, $c_9=c_8\cdot c\bmod n\;$, $c_{18}={c_9}^2\bmod n\;$, $c_{36}={c_{18}}^2\bmod n\;$, $c_{72}={c_{36}}^2\bmod n\;$, $c_{73}=c_{72}\cdot c\bmod n\;$, $c_{146}={c_{73}}^2\bmod n\;$, $c_{147}=c_{146}\cdot c\bmod n\;=m\;$.

With $c=288\;$, we compute $c_2=903\;$, $c_4=657\;$, $c_8=698\;$, $c_9=165\;$, $c_{18}=821\;$, $c_{36}=739\;$, $c_{72}=124\;$, $c_{73}=821\;$, $c_{146}=739\;$, $c_{147}=657=m\;$; we then discard the rightmost digit giving $65$, and fetch the ASCII table to be back to A.

Notes:

Random padding is a necessary step in secure RSA encryption; the minimalist scheme used here is enough to hide repeated uses of the same symbol (with odds 9/10 for any pair of uses of the same letter). Many RSA illustrations with artificially small parameters omit random padding, thus are very vulnerable to construction of a dictionary of plaintext letter to ciphertext block, using only the public $(n,e)$.
With the artificially small parameters, and even though we are at the upper-end of the 10-bit limit of the question, there are two major weaknesses:

it is trivial to factor $n$ to yield $p$ and $q$ and compute a working $d$; we'd need to go to at least 320 bits to make this attack even so slightly challenging.
it is also possible to compute the 10 possible encryptions for each symbol (perhaps starting with the most common ones); this attack turns out to be easier than the normal decryption procedure for message of any significant size; larger parameters allow to fix this, see 6.

The condition $e^2\bmod\operatorname{lcm}(p-1,q-1)\ne1$ ensures that the public key can not be used as private key, which is all too common in artificially small RSA examples, and would introduce confusion in the audience if anyone tries it, perhaps by accident. Checking this condition is pointless in real uses of RSA, because it is true with overwhelming odds.
$d\equiv e^{-1}\pmod{\operatorname{lcm}(p-1,q-1)}\;$ is the necessary and sufficient condition for $d$ to be a working private exponent, and tends to ease calculations.
A spreadsheet such as Excel is suitable for such explorations, including with slightly less small parameters; it can easily handle modulus $n$ up to at least 25 bits; =MOD(A1*A2,A3) will compute $A_1\cdot A_2\bmod A_3$ exactly and =MOD(MOD(A1*A1,A3)*A1,A3)will compute ${A_1}^3\bmod A_3$ exactly, assuming $A_1$, $A_2$, $A_3$ are at most 24-bit.
Suitable parameters with 25-bit modulus are $n=28157923=4967\cdot5669\;$, $e=3\;$, $d=360863\;$; that allows encoding $0\le m<2^8$, with 5 decimal digits of random padding instead of 1.


Implementing commitments and challenges for a distributed ElGamal encryption scheme

I can't access the book, so not sure exactly what it says, but the article you referenced also seems to be generating values in a group with order q: my intuition is that they are just using separate variables and group is of the same size in both texts just using $q$ and $p$ as variables respectively. As long as you are sampling $x_i$ uniformly from the full modular group you should be okay.

A for using modulo p, the security of El Gamal relies on the hardness of discrete log within the group $G$ with order $p$, so all operations are bounded via $\bmod p$.

Hope this is helpful, did I understand your question correctly?


What's the point to build a cheap NAND gate ?

Because it's a complete operation; you can build any circuit with a sufficiently large pile of them.

  Maybe to build cheaper AND and OR gates based on this NAND gate and then follow the approach of Regev's type cryptosystems?

You could build AND and OR gates with them (and INVERT; AND and OR by themselves are not complete); however you'd probably be better off designing the larger circuits directly with the NAND gates.


Is a modulo addition safe for the encryption of private keys?

Note: I will not talk about potential implementation flaws in this answer but rather about the conceptual way to approach this problem.

OK, so what you have a 256-bit hash function $H$ (Keccak) and what you need is a (somewhat) secure password-based encryption scheme that from what I could guess avoids operations on bit-wise data.

So what should be used is really CTR-mode with a Keccak-MAC and an iterated Keccak for password-based key-derivation purposes. I shall now discuss these three components:

Iterated Keccak PBKDF. Right now the code does $k\gets H(s\parallel p)$. This means an attacker has to do exactly one evaluation of the (fast) hash function to verify a password guess. This is way too fast, as users tend to choose weak passwords which then get brute-forced quickly. If you want to read further into this, this is basically equivalent to "salted, plain MD5". Now for the solution: As you seemingly can't afford to use a proper password hashing scheme, your best choice is to use PBKDF2 with Keccak as your PRF, ie your PRF would be $F(k,x)\mapsto H(k\parallel x)$. I expect this to only take a few lines and you can re-use your salt. As for the iteration count, you should adjust it such that the derivation takes roughly 100ms.
Keccak-CTR. Right now your code iterates over all nibbles and adds the "noise" that was generated by the hash function call. This is safe (in theory), however it only works as long as the output of the hash function and the size of the data object in question match. If they don't anymore, you really want to use CTR-mode, or rather want to use $c_i\gets p_i\oplus H(k\parallel i)$ for blocks of the size of a hash function output. I also have to recommend against using the key directly as the "pad" for the data, but rather that it is run through the hash function once more, the reason being cryptographic key separation (and it doesn't scale as mentioned above).
Keccak-MAC. Right now you wouldn't nice manipulations on the key, which could potentially lead to keys being more easily attackable or just "simple" denial-of-service attacks. This is why you should use cryptographic authentication. Doing so is actually quite simple, due to Keccak being a sponge construction: $\tau\gets H(k\parallel s\parallel c)$, ie the authentication tag is the result of the concatenated hash of the key, the salt and the cipher text. Append this to your output and verify the consistency of this value on loading and you can rest assured that it hasn't been tampered with.


Can keys from Bitcoin's Hierarchical Deterministic Wallets be correlated (reducing privacy)?

I recently came across a paper that may interest you that I think answers your question. To quote from the abstract:

  Unfortunately, in all existing HD wallets---including BIP32 wallets---an attacker can easily recover the master private key given the master public key and any child private key. This vulnerability precludes use cases such as a combined treasurer-auditor, and some in the Bitcoin community have suspected that this vulnerability cannot be avoided.

Combine this with the fact that child private keys are generated from the master private key, and it appears the answer to your question is no, they do not offer complete privacy.


What is the diffrence between Feistel networks and SPN?

In a Feistel networks (from the German IBM cryptographer Horst Feistel), the input is divided into two blocks ($L_0$ and $R_0$) which interact with each other. Main example is DES.

basic construction:

In a SPN (Substitution Permutation Network), the input is divided into multiple small blocks, applied to a S-box (substitution), then the bits positions are mixed (permutation). The key addition may occur before or after these two operations.

Present block cipher:


Is chosen ciphertext attack used to obtain a key?

Chosen Ciphertext Attack is typically not used to obtain a key, but rather to obtain plaintext, or partial information about plaintext. Getting at the key is sufficient, but not necessary, to claim success of a CCA attack.

Indistinguishability under Chosen Ciphertext Attack is a theoretical model of attack. The attacker is assumed to be able to obtain decryption of ciphertext s/he chooses, under the key being attacked; and succeeds if s/he manages to gets any kind of information about plaintext corresponding to ciphertext s/he did not previously submit for decryption. Formally, the attacker succeeds if s/he recognizes better than random which of two ciphertexts s/he submited for decryption was selected by a referee, who produce the result of its decryption. Of course, getting at the key allows that.

In the most stringent variant CCA2, the attack is iterative.

That model may seem of theoretical interest only: if the adversary can obtain decryption of ciphertext s/he chooses under the key considered, it may seem that all security is lost. So why care against that?

Because we can, at little cost. A simple way to achieve CCA2 security is to use authenticated encryption. Essentially, decryption is forced to fail (and the deciphered plaintext is not released) if the ciphertext was crafted or altered by a party not holding the key.
Because CCA2 security does guard against plausible attacks. I'll take the example of efail. The context is hybrid cryptography, where a message is sent symmetrically encrypted using a random message-unique key, itself sent along the message encrypted with the public key of the receiver(s). The receiver of the message (and the email program + extension used for deciphering OpenPGP or S/MIME) is tricked into leaking some of the decryption of altered ciphertext (e.g. by way of accessing an internet server at an URL in the deciphered plaintext). The alterations are focused on the symmetrically-encrypted payload, thus the decryption is carried with the original key.


Key exchange protocol and digital signatures

No, the Diffie-Hellman key exchange protocol by itself does not include any use of digital signatures.

However, Diffie-Hellman is also insecure against man-in-the-middle attacks, because the messages are not authenticated. This should give you a pointer what to do with the digital signatures.


Block cipher linearity (in relation to hill ciphers)

Yes, you can convert the Hill Cipher into almost any mode of operation. For simplicity, assume that $M$ represent the key matrix and $P$ represent the plaintext vector and $C$ is the corresponding ciphertext vector with $C = M\cdot P \pmod{26}$. For simplicity, we omit the mode 26 for the rest.

ECB mode: we can assume that Hill cipher is already in ECB mode. As usual, divide the message into the correct matrix size, you also need a padding scheme.
CBC mode: generate an $IV$ which must be unpredictable, however, this is your least concern, as usual, $ C_0 = M\cdot(P_0\oplus IV) \text{ and } C_i = M\cdot(P_0\oplus C_{i-1})$. You also need a padding scheme.
CTR mode: $C=P \oplus [M \cdot  (\text{nonce ||  Counter})]$. Here one may need to take care of the counter since it is a Matrix. One can consider each cell of the Matrix as a mod 26 counter. No need to padding.
CMC-MAC: Since you have CBC mode, you have it, now. Remember, in CMC-MAC the IV is all zero.

Note 1: For CBC-MAC we don't need just AES, we can use any secure block cipher.

Note 2: the $\oplus$ can generate a number greater than 26. You need to use $+ \bmod26$

And a final note: The Hill cipher is vulnerable to known-plaintext attack which means that it is broken! You cannot build a secure mode of operation from a broken cipher!


Lower bound of key space size with relaxed perfect secrecy

Oddly enough, if the equation holds for any $m_0, m_1$ of the appropriate length, it would appear that relaxing this requirement doesn't allow us to shrink the key size at all (!).  That is, the key size must still be as long as the plaintext size (or, more precisely, there must be at least as many possible keys are there plaintexts).  Allowing a value of $E > 1$ turns out not to allow us to use smaller keys; OTP is still an optimal solution for the requirement.

Here's why: this requirements still requires plaintext $m_1$ to have nonzero probability (as if it doesn't, then the equation can't hold if $m_0$ is any plausible plaintext).  Any, if there were fewer keys then plaintexts, that would mean that some plaintext is impossible (and hence have zero probability).  Because that can't happen, that means that there must be at least as many keys as plaintexts.


Does FHE's longer key bring more security than traditional encryption algorithm?

No, the large sizes basically come from the fact that one needs to be able to handle a very large error term in order to perform a procedure known as "bootstrapping." The basic idea of bootstrapping is that we use a "base" homomorphic system which is somewhat error-prone; that is, the decryption of $c_1 \oplus c_2$ is intrinsically some $m_1 + m_2 + \epsilon$ for some error $\epsilon$. As we evaluate more and more $\oplus$ gates we accumulate more and more error, but we can solve this problem by including more and more bits per "signal" bit to handle the "noise" bits, and there are even clever ways to shift moduli as-you-go to keep the absolute magnitude of the error down for multiplications and so forth -- what's important is that you can either limit the depth of the circuits you use, or increase the size of the state space. Finally as part of decrypting, we end up truncating this error.

In bootstrapping, we take the fixed ciphertext that we have built up so far (which we of course know) and we form the circuit which would take a variable private key (which we of course don't know) and decrypt this ciphertext with that key. So, we "homomorphicize" this decryption circuit by treating the key as the input and the ciphertext as fixed, known boolean constants. We can then apply the homomorphic circuit to an encrypted private key $\kappa = E_k(k)$ that is stored as part of the public key, to get an "encrypted decrypted ciphertext" -- in other words, to get a new representation of our fixed ciphertext, $c \mapsto c'.$

This sounds completely useless and it is completely useless if you do not include the homomorphic version of the logic which truncates the error. But when the homomorphic error-truncation logic enters the picture, something magical happens: whatever $\epsilon_c$ has been built up so far in $c\leftrightarrow m + \epsilon_c$ gets replaced with a fixed error, $c'\leftrightarrow m + \epsilon_0.$ This error only depends on the depth of the decryption circuit (when viewed in this backwards key-first way).

I like the analogy for bootstrapping that one of the TFHE researchers gave: Spider-man can only swing for a certain time on one piece of webbing before it "runs out" (and he starts going backwards or something). But Spider-man is able to swing an arbitrary time/distance. How does he do this? While he is swinging he devotes some of his time to firing out another piece of webbing, and switches to that before the current piece "runs out". Similarly we have an error threshold of operations; we can only continue for a certain number of operations before we "run out", and so we devote a certain number of these operations to resetting our error bars on our ciphertext state and then we can continue doing this again.

Anyway, for a long story short, the combination of the tolerable error margins and the width of the key/plaintext/ciphertext together set the security level; and you may need to increase the width of the key text without making the key any more secure, in order to handle larger homomorphic circuits. The docs for the TFHE software for example specify that they target only a 110-bit security level; that places its security roughly at the 2048-bit RSA level according to a 2003 estimate from RSA security. The fact that it has megabyte-size keys is purely to handle the errors needed to bootstrap successfully.


Someone else should chime in here just to be sure, but as far as I know truncating SHA256 is "safe", in the sense that it would be as good as any other "safe" 128 bit hash. I don't think XORing helps in any way, dropping the bits is probably better. Your application of a truncated SHA256, however, is not safe.
Yes, there is absolutely a better way. Like you said, average password entropy is low. Your key therefore has low entropy. Brute forcing a low entropy key is easy, when the key derivation is a simple SHA256 round. You need to use a specialized password hashing function. SHA256 is designed to be fast, you need a function that is designed to resist such brute force attacks. Examples include Argon2, scrypt, and PBKDF2.
This depends on the design. An IV should not be predictable. What kind of password would you be using to generate an IV? Would you use it multiple times? Are there reasons why you can't use a random IV?


Can I use HMAC-SHA1 in counter mode to make a stream cipher?

Yes, this would be secure. CTR (Counter) mode based on keyed function $F_K$ is secure as long as its output
$$
W_i = F_K(i)
$$
is unpredictable given previous outputs
$$
F_K(1),F_K(2),\ldots,F_K(i-1).
$$
This requirement is essentially the definition of a pseudo-random function (PRF). Most HMAC instantiations with widely used hash functions are believed to be secure PRFs (rigorous proofs are impossible for several reasons).

You may have heard of CTR mode as a blockcipher mode. This is also correct, as a secure block cipher must be a secure pseudo-random permutation (PRP), which can not be distinguished from PRF if it is queried/used fewer than $2^{n/2}$ times, where $n$ is the block size.

Block ciphers are used in CTR mode primarily due to their speed (HMAC is slower, in particular on short messages), but keyed hash functions are equally strong.

Certainly, you must ensure that your counter never repeats. You may want to follow the NIST strategy (page 18) of constructing the counter from nonce.


Does it mean that the input is any length of zeros and ones and that is should hash to a value which is 3000 digits of zeros and ones?

Yes, that's the meaning of $\{0,1\}^*→\{0,1\}^{3000}$. It would be better to reformulate using the usual shortcut for "digits of zeros and ones": bits. Also, $\{0,1\}^*$ is the set of all bitstrings.

  Could I just apply SHA-256 12 times, splitting the input in 12 parts and remove 72 bits, then I will get 3000 bits?

$256\times12-72=3000$, thus you have the domains right. But would that be indistinguishable from a random oracle¹? No. Find how you would make the distinction. Then improve that construction. Ideally, make a proof that if a method could distinguish the refined construction from a random oracle¹, then it could be turned into a method making that distinction for SHA-256.

A random oracle with $k$-bit output is an hypothetical device that accepts a bitstring as input, and

if that bitstring was not previously submitted, draws and outputs a random bitstring in $\{0,1\}^k$
otherwise outputs the same bitstring as it did for the previous submission of the input bitstring.

¹ With no way to compute SHA-256, and perhaps disregarding the length-extension property of SHA-256, and its input length limitation; some or all of these might be what the question means with "(almost)".


Known Plaintext Attack against 3-round SPECK48/96

Here is how I would approach this:

First off, strip off the unkeyed parts of the cipher at the beginning and the end.  That is, process the plaintexts with the 'rotr 8/add/rotl 3' at the beginning, and process the ciphertexts with the 'xor/rotr 3' at the end (rotr because we're working the inverse direction).
Next, we focus in on only the right side ciphertext output; this allows us to skip the entire third round (!)

With these two simplifications, the remaining cipher has only one nonlinear step (the addition in round 2).  We proceed to attack that.

The obvious way to start is looking at bit 0 of the addition (we start at the lsbit because there's no carry from unknown bits; if we were doing a differential attack, we'd start at the msbit, as a differential in the msbit propagates with probability 1); the addend on the vertical path is the xor of 1 known bit and 1 key bit; the addend from the right side is the xor of 2 known bits and 1 key bit; we can deduce the lsbit of the sum from xor of 2 known plaintext bits, 1 known ciphertext bit, and 2 key bits (one from subkey 1, the other from subkey 2).  We know that the two addends are consistent with the sum, so we go through all 5 possibilities of the key bits, and see which settings are consistent with all known plaintext/ciphertext pairs.

Now, it turns out that addition in the lsbit is actually linear, and so there will be 16 possible settings for the key bits that'll be consistent, but that's OK.

Now, we extend the attack to bits 0 and 1 of the addition; the addends and the sum are also functions of a known plaintext/ciphertext bits, and a handful of key bits, and so we go through those possibilities, and eliminate those which aren't consistent with the known plaintext/ciphertext pairs (and now that there's real nonlinearity, they'll be some considerable pruning).

I could go on, but it should be fairly obvious where to go from here...


If you just encountered the term, I would suggest that you get used first to the intuition of how it can be achieved. ZK using graph isomorphism is great as an introductory example (although impractical for more cases).

That said, what you are looking for is known as [Yao's] Millionaire's Problem. The description of the problem talks about two millionaires who want to find out who is the richest of them without disclosing their actual wealth.

I believe that, for your problem, it is not zero knowledge what you're looking for. Look instead for multiparty computation, but beware: this is a huge research area. In MPC, you want multiple entities to interact, but you know that some of them can cheat in very different ways. The literature is strongly associated with e-voting. You will meet there with Zero Knowledge, but also with homomorphic encryption, commitments and other concepts. You'll be specially interested in oblivious transfer: Bob knows a function $F$. You, Alice, want to get the value of $F(n)$ without telling Bob the value of $n$.

There are different ways to approach the problem, each with a set of trade-offs. You can start at the Wikipedia page about the problem and come back later if (when) you have more questions. It all depends on the capabilities of your adversary. After all, you could just ask the two millionaire's independently in separate rooms and tell them who is the richest without disclosing their values, without using any crypto!


No, it would not reduce the size of the keys.  To break an ECRSA problem, you would factor the order; that factorization problem is not inherently different than any other factorization problem over the integers.  Hence, to make that problem intractable, you'd need to make it as large as traditional RSA.


Convincing "someone" on the (in)validity of DH tuple without revealing $u,v$

That depends on the groups you are working in.

Using a $\Sigma$-protocol

If you have a group $G$ of prime order $q$ where the DDH is hard and you have a DH tuple $(g,g^u,g^v,g^w)$ with $w\equiv uv \pmod q$, then if your prover
knows one of these values, say $u$, then we can write the DH tuple as $(g,g^u,h,h^u)$ and he is able to
convince a verifier that this is a DH tuple by means of a standard $\Sigma$-protocol, see here (Section 5)
for a concrete protocol. This proof can be made non-interactive by using the Fiat Shamir heuristic.

Gap DH Groups

If you are working in a gap Diffie Hellman group setting, i.e., a setting where the DDH is easy but the CDH is still hard, that is easy without interactive proofs. I use additive notation for groups $G_1$ and $G_2$ below as we are talking about elliptic curve groups.

For instance, take a symmetric cryptographic pairing $e:G_1\times G_1 \rightarrow G_T$ where $G_1$ is an elliptic curve group of prime order $p$ and $G_T$ a multiplicative subgroup if a finite field of the same order $p$. Then $G_1$ is a gap DH group.

Then given $(P, uP, vP, wP)\in G_1^4$ you can check if this is a DH tuple by checking if $$e(uP,vP)\stackrel{?}{=}e(wP,P).$$

Same works for an asymmetric type-2 pairing $e:G_1\times G_2\rightarrow G_T$, where you have an efficiently computable homomorphism $\psi: G_2 \rightarrow G_1$. Here $G_2$ is a gap DH group and when given a DH tuple $(P', uP', vP',wP')\in G_2^4$ you can efficiently check it by checking $$e(\psi(uP'),vP')\stackrel{?}{=}e(\psi(P'),wP').$$

Side note (which at least I find interesting)

An interesting side note is that the Chaum Pedersen signature scheme uses the first approach in DDH hard groups, where the proof is made non-interactive by using the Fiat Shamir heuristic. Here, the DH tuple to check is $(g,g^x,m,m^x)$ where $\sigma=m^x$ is a signature for $m$ w.r.t. public key $h=g^x$ and they require a non-interactive proof $\pi$ that $\log_g h=\log_m \sigma$, i.e., to prove that the signer actually knows the secret key $x$.

The BLS signature scheme essentially does the same in gap DH groups where they do not require this non-interactive proof $\pi$, but can use the pairing $e$ for checking the DH tuple. However, they have to hash the message to a group element using a secure hash function $H$, as the direct application of the Chaum Pedersen approach would make the signature scheme insecure (as otherwise one could forge signatures without the secret key). Here the DH tuple to check is $(P,xP,H(m),xH(m))$ where $xH(m)$ is a signature for $m$ w.r.t to public key $xP$.


Static ciphertext length for any plaintext length less or equal than x?

If you can give up two bytes (so the longest message is 1022 bytes long), then this can be straightforward.

Create a 1024-byte buffer. Make the first two bytes the length of the message. Then add the message. Then pad the rest of the buffer with random data. Random data is best here because it leaks less information than zeros, but you could use zeros.

Encrypt the entire buffer. When you decrypt the result, pull the first two bytes and use that to extract the right number of bytes.

This of course will work for any length; so if you need a full 1024-byte message, you can just make the ciphertext always be 1026 bytes.


Could symmetric keys be of sizes other than 2^x or 2^x + 2^y?

Modern CPUs are typically 64-bit. This gives us a very good performance incentive to design symmetric cryptography with block size as a multiple of this.
There is a lesser (IMHO) drive for using $2^x$ bits, many parts especially in hardware will require ceil(log(length)) time/depth/gates by using $2^x$ we get more efficient implementations.
Obviously we could build a less efficient (bytes/second or bytes/$) cipher with arbitrary block size.


How can a cyclic group have two generators?

I believe part of the difficulty you are running into is because, in cryptography, we use the word 'generator' in multiple distinct (albeit related) ways.

One meaning (which is what is intended here) is this: we say that an element $g$ is a generator for a group $G$ if the group of elements $\{ g^0, g^1, g^2, ... \}$ is precisely the group $G$; that is, every element $h \in G$ can be expressed as $h = g^i$ for some $i$, and conversely, for every $i$, $g^i \in G$ [1].

Now, the obvious question is: for a given cyclic [2] group $G$, is the choice of $g$ unique?  It turns out that (as long as the order of the group is > 2) it is not.  In fact (as mentioned in the comments), if the size of the group is prime, then every group element (other than the identity) happens to generate the entire group, and so (in this sense) there are also generators.

Now, to give you some perspective, I will give you another meaning we give 'generator' that isn't meant by this question.  Sometimes, in a cryptographic protocol, we need to specify a public generator $g$ that will be used by both sides.  A simple example of this is Diffie-Hellman, where one side computes and publishes $g^a$, and the other side computes and publishes $g^b$; both sides must use the same $g$ value for this to work.  We call this common value the generator; yes, there are other values that are (in the first meaning) also generators for the group we're working in, however, they are not the generator as far as protocol is concerned.

[1]: for infinite groups, we also need to consider negative exponents; we don't worry about infinite groups that much in cryptography.

[2]: actually, the definition of a cyclic group essentially is "there exists a generator"


Is there a name for encrypting a decimal number using a one time pad?

The correct names are OTLP (one time letter pad) and OTFP (one time figure pad). More about the system here:

http://users.telenet.be/d.rijmenants/en/onetimepad.htm


How to use salt if I am sending hashed password?

Ask the server for the salt for a specific username.
Compute the expensive salted hash on the client, send to server
Server performs a cheap unsalted hash(or HMAC) on the hash received from the client and compares with the stored value

Note that sending a hashed password doesn't mean you can use an insecure transport. You still need proper transport security, such as SSL/TLS/HTTPS or a specialized password verification protocol such as SRP.


Is a padding oracle attack possible if data is only encrypted internally on a server (e.g. for storage)?

As far as I can tell, you just have encrypted data in a DB and are worrying that it can be hacked. In short, encryption works so you're good.

In more detail, your analysis of a padding oracle attack is correct. As you don't have any services or APIs or network protocols that partake in the encryption, a padding oracle attack can't occur.

Understanding that I don't fully understand your architecture, I can tell you about the attacks I'd worry about:

There are potential client-side attacks. Perhaps via OS or browser malware. Not your app's fault but can still lead to an exposure of your data.
If you have a malicious admin, they could attack your application directly. They could potentially modify your class files to extract your data while it's in motion. Worse, they can call your decryption functions to bulk decrypt the DB.
Examination of your app's memory to look for secure data or the encryption key.
Examination of your app's configuration to get your decryption key.
An application vulnerability that allows a remote attacker to extract data from your app or cause it to perform malicious actions. This may be the biggest threat as it allows for remote attacks.

I'm sure there's more but that's my quick evaluation. I think that the breaking the DB encryption is far down the list of things to worry about. Secure your key (preferably in a password-sealed keystore) and secure your app against a remote attack.


Can the original data be extracted from an RSA private key signed message

Whenever you see the letters ECB, you should run away screaming.  This is a telltale sign that something has gone terribly, horribly wrong.  The code fragment you quoted implements what we sometimes call ‘textbook RSA’, which is a polite way to discreetly announce to the cocktail partygoers that you are desperately in need of a professional cryptographer.

This is not your fault: whoever designed the Java API that requires you to specify ECB in a string and which you will use to ‘encrypt with the private key and decrypt with the public key’ (which is a contradiction in terms that makes cryptographers twitch involuntarily, sometimes leading to a cocktail dribbling down your face and shirt) did not have the decency to ask for a professional opinion—which is what you are more or less doing now!—before they inflicted a monumentally wrong confusion of ideas into an API set in stone.

Let's back up a moment.  What do you and your peer have in common, and what security do you want?

If you share a secret already, and you want to exchange unforgeable and possibly secret messages, what you want is a symmetric-key authenticator like HMAC-SHA256, or a symmetric-key authenticated cipher like AES-GCM or NaCl crypto_secretbox_xsalsa20poly1305.  But you mentioned public keys, so maybe you and your peer don't share a secret yet—maybe all you have is your respective public keys, which are known to be correct but are not secret.
If you share a public telephone book with public keys, and you want to exchange unforgeable and possibly secret messages, what you want is public-key key agreement like X25519, which is a way for you to use your private key and your peer's public key in the telephone book to compute a secret, which can also be computed by your peer using their private key and your public key in the telephone book so that you and your peer have a shared secret; or you want public-key authenticated encryption, like NaCl crypto_box_curve25519xsalsa20poly1305, which works by stringing together public-key key agreement (X25519) and symmetric-key authenticated encryption (crypto_secretbox_xsalsa20poly1305).
If your peer has a public telephone book where you are named, and you want to send a message to your peer that your peer can show to a third party and convince the third party it came from you, then what you want is public-key signatures like Ed25519.

You could also use an RSA-based signature scheme like PKCS#1 v2.1 RSASSA-PSS, but unless you have a specific technical reason motivating the use of RSA, you are better off using the smaller faster safer Ed25519, unless the cost of verification is your principal bottleneck.
If you have a public telephone book where your peer is named, and you want to send a message to your peer anonymously so that only your peer can read it but not necessarily verify it came to you, then what you want is public-key anonymous encryption like NaCl crypto_box_curve25519xsalsa20poly1305 with an ephemeral public key.

You could also use an RSA-based encryption scheme like PKCS#1 v2.1 RSAES-OAEP, strung together with an authenticated cipher like AES-GCM, but unless you have a specific technical reason motivating the use of RSA, you are better off using the smaller faster safer NaCl crypto_box_curve25519xsalsa20poly1305 with ephemeral keys, unless the cost of encrypting messages is your principal bottleneck.

But OK, let's suppose you are using some RSA signature scheme.

Any serious RSA-based signature scheme involves hashing the message.  The simplest one, RSA-FDH, uses a hash function $H$ that hashes messages into all or nearly all of the set $\{0, 1, 2, \dots, n - 1\}$; a signature under public key $n$ on a message $m$ is an integer $s$ such that $s^3 \equiv H(m) \pmod n$.  From the signature $s$, even if you don't have the message $m$, you can recover $H(m)$ simply by computing $s^3 \bmod n$, but if $H$ is a good hash function this doesn't help to recover $m$.

With RSASSA-PSS, the equation is more like $s^3 \equiv 2^t r + H(r \mathbin\| H(m)) \equiv n$, where $H$ is a smaller hash function like SHA-256.  Again, you can recover $H(r \mathbin\| H(m))$ this way, but not $m$.

There are some ‘message-recovery’ variants of RSA signature schemes, in which some part of the message $m$ is embedded in $s$ alongside $H(m)$, but they are not widely used and you would probably know if you were using one.

All that said: Usually what you do is send a signed message, i.e. a message alongside its signature; otherwise, how does the recipient act on the message, or even find what message the signature corresponds to?  And if you do that, there is nothing a priori that prevents anyone but the intended recipient from reading the message—after all, in a signature, only the sender's keys are involved.

You can combine public-key signature and public-key encryption, but this is usually a bad idea for two reasons:

A secure composition is hard to get right; OpenPGP and S/MIME got it wrong.
Public-key signature also usually guarantees that third parties can verify messages, which is usually not what you want for private conversations.

So, you are most likely better off using NaCl crypto_box_curve25519xsalsa20poly1305, which does it all in one: combines you private key, your peer's public key, a 192-bit message number, and a message, and returns a ciphertext that your peer and only your peer can check for forgery and decrypt.


Could quantum computers "break" symmetric crypto-systems (e.g. AES)?

With Grover's algorithm, quantum computers can brute-force a block cipher with $n$-bit keys using $2^{n/2}$ steps, which is much smaller than the regular effort ($2^n$). This means, for example, that AES-128 could be broken with $2^{64}$ steps, and that AES-256 would offer the same security that AES-128 offers currently.

In short, key sizes would need to be doubled.


Generating unsigned, bounded random value using signed bounded random values

I assume $R(x)$ is the original generator, returning $r$ uniformly distributed with $0\le r<x$ for $x<2^{n-1}$, as does Java's int nextInt(int) for $n=32$; and we want to extend that to $R'(y)$, returning $r$ uniformly distributed with $0\le r<y$ for $y<2^n$. $R$ and $R'$ should treat an argument less than $2$ in the same way (perhaps accept it and return $0$, or reject if somehow). Out of laziness I'll only handle $n$ even and $n>2$, which covers practical use cases.

If $y<2^{n-1}$, $R'(y)=R(x)$ is fine.

If $y=a\cdot b$ with $a>1$ and $b>1$, $R'(y)=b\cdot R(a)+R(b)$ is fine. That is useful when $y$ is known at compilation time and composite.

Else (when $y\ge2^{n-1}$ and prime), there is no method guaranteed to work with a finite number of invocations of $R$, and we must use some iterative method.

Out of my head (not tested), a possible line of action when $y$ is known only at runtime:

if $y<2^{n-1}$, return $R(y)$.
if $y$ is even, return $2\cdot R(y/2)+R(2)$.
if $y=2^n-1$, return $(2^{n/2}-1)\cdot R(2^{n/2}+1)+R(2^{n/2}-1)$.
repeat

let $r:=R((y+1)/2)$
if $R(2)\ne0$, return $r$.
if $r\ne0$, return $y-r$.

Notes:

With the assumption that $n$ is even, we can handle $y=2^n-1$ as $(2^{n/2}+1)\cdot(2^{n/2}-1)$.
When $R((y+1)/2)$ is computed, this is valid since $1<(y+1)/2<2^{n-2}$.
At each iteration of the loop (which occurs only for odd $y$), the value returned (if any) is correctly distributed because:

$r$ is returned with odds $1/2$, and then is uniform on $[0\dots(y-1)/2]$
$y-r$ is returned with odds $1/2-1/(y+1)$, and then is uniform on $[(y+1)/2\dots y-1]$
the "repeat" loop continues with odds $1/(y+1)$, which is at most $1/2^{n-2}$, and thus low for practical $n$.

We can lower the expected number of calls to $R$ (by $46\%$ for $n=16$ and $2^{n-1}\le y<2^n-1$) by accumulating $n-2$ uniform bits (and a sentinel) in a variable $b$ surviving across invocations, set to $0$ initially (in the C programming language, that could be static short b = 0; in the body of a function). It is however at the expense of increased complexity, and perhaps of thread-safety, and thus a bad idea in most practical situations! The algorithm (not tested) can become:

if $y<2^{n-1}$, return $R(y)$.
if $y=2^n-1$, return $(2^{n/2}-1)\cdot R(2^{n/2}+1)+R(2^{n/2}-1)$.
repeat

let $b:=\begin{cases}R(2^{n-2})+2^{n-2}& \text{if }b<4\\\lfloor b/2\rfloor&\text{otherwise}\end{cases}$
let $r:=R(\lfloor(y+1)/2\rfloor)$
if $b$ is even, return $r$.
if $y$ is even, return $y-1-r$.
if $r\ne0$, return $y-r$.


Is my HMAC secure if I have a complete series of HMAC'd prefix strings

I'll start by assuming that your instance of HMAC is a secure MAC function, which comes down to making various assumptions about the hash function it is instantiated with.

If this assumption holds, then an adversary will not be practically able to recover the key, even if they have access to a large number of MACs and the corresponding plaintexts, or even if they get to choose their own plaintexts — if it was possible for them to obtain the key, they'd be able to compute their own MACs and thus commit existential forgery, contradicting the assumed security property.

As for plaintext recovery, in general there's nothing that prevents a MAC function which is secure against existential forgery from leaking some information about the input plaintext, and indeed it's not hard to delibrately construct examples of such MACs (as Ricky Demer's answer shows).

However, the security proof of HMAC given by Bellare actually proves a stronger property, namely that HMAC is a PRF as long as the compression function of the hash it is instantiated with is also a PRF (or, more generally, than HMAC is a privacy preserving MAC (PP-MAC) as defined by Bellare, as long as the compression function is also a PP-MAC and the hash function itself is computationally almost universal (cAU); see remark on Lemma 4.2).  This is a rather strong security property, and it indeed shows that, as long as the hash function satisfies the assumptions of the proof, HMAC will not leak information about the plaintext to an adversary who does not possess the key.


Brute forcing an elliptic curve encrypted key

Doesn't this mean we could attempt to brute force a private key by using:
  $$\mathit{privKey} = \mathit{pubKey}/G$$
  for all potential values of $G$?

There seems to be a misunderstanding here: $\mathit{pubKey}$ and $G$ are fixed and publicly known, so there's nothing left to brute-force. The operation of "dividing" $\mathit{pubKey}$ by $G$ is (to the best of current public knowledge) computationally infeasible; this is the elliptic-curve discrete logarithm problem (ECDLP).
However, of course, one can brute-force by trying all possible values of $\mathit{privKey}$ and checking whether $\mathit{privKey}\cdot G=\mathit{pubKey}$ holds.

  what if by chance that one of the first few attempts happened to have the correct value?

This is very much related to this recent question. The bottom line is: Yes, that could happen, but the probability is so incredibly low it is never going to occur in practice. (And in any case, if we're worried about someone just guessing our secret keys by pure luck, there's nothing anyone could do against it anyway.)


Third-party security issues with Shamir's secret sharing scheme

We simply have to trust this party because this scheme requires a trusted dealer (a party that distributes the shares to the secret to the participants - this can be you or some other party - but if its you you should trust yourself).

We can use verifiable secret sharing, that allows the parties to check whether the shares they have obtained are consistent, i.e. to verify if the dealer behaves honest (but the dealer still knows the secret and thus this is only a partial reduction of trust).

If we do not want to have a trusted dealer who sets up the shares at all, we have to switch to dealer-free secret sharing schemes. See for instance, here.


Forgery Attack Against RSA Digital Signature

why the attacker can't control the message??

Well, if he could control the message, that is, given the value $x^e \bmod N$, find $x$, well, he just solved the RSA problem, and we believe that he can't do that, or at least, he can't do that in any modulus that we expect is secure.  Yes, you can do a brute force search over a $N$ as small as 11021; that indicates that such an $N$ is too small to be used for RSA.

  And what if Oscar send to Alice his public key instead of bob's ?? How does the RSA Digital Signature protect against such an attack??

If Oscar sends his public key to Alice, and Alice does accept it as Bob's key, then yes, Oscar will be able to sign any message, and Alice will mistakenly believe it came from Bob (because it was signed using what she thought was Bob's key).

How does RSA protect against this?  Answer: it doesn't; that's a problem that RSA assumes that is protected against by some higher level protocol.

The issue is "how do we bind a public key, which is a bunch of bits, to an identity in way that we can trust".  There are a number of ways to address this.

One such way (which is fairly common in practice) are certificates; we have a message that states "Bob's key is [public key], as attested by Trent", and that message is signed by Trent.  If Alice trusts Trent, then Bob (or Oscar) could send that certificate to Alice, and she can validate what the certificate says (because she trusts Trent).  Oscar cannot generate a certificate with his key and Bob's identity, because Trent will not issue such a certificate (and Oscar can't fake Trent's signature on something he can generate).

There are other ways of solving this as well; that you solve it is obviously crucial.


Diffie-Hellman: Recommendation of the base size?

The standard approach is to use $N \equiv 7 \pmod 8$ so that $a = 2$ has order $p$ by virtue of being a quadratic residue, e.g. in the RFC 3526 groups, chosen by the deterministic procedure described in RFC 2412, Appendix E.  Using any other groups for finite-field Diffie–Hellman raises a lot of eyebrows.

Uniform random exponents of the usual size have negligible probability of being small enough to admit their recovery by real number logarithm computations: even for $a = 2$ and $N \sim 2^{2048}$, the probability of a 256-bit exponent admitting this attack is about $2^{11}/2^{256} = 2^{-245}$ which is a technical word for ‘not gonna happen’.

Of course, you should just use a modern system like X25519 instead of finite-field DH anyway!  Faster, safer, simpler.


Why do $\alpha$ and the private key value in diffie-hellman should be from $2$ to $p-2$

The reason for both is that the generated values are trivial to detect / exploit and should be avoided and your RNG is deeply flawed if you actually get those values because the chance for this lies around $2^{-2000}$ if you use an appropriate parameter set.

Now for the math:
You need to choose your secret exponent $x$ such that $1\leq x\leq p-2$, with $p$ being the prime defining the multiplicative Field $\mathbb Z_p^*$. Your generator $\alpha$ needs to be chosen such that $2\leq \alpha \leq p-2$. The source for these constraints is the famous Handbook of Applied Cryptography, 1996, Menezes et al (page 516).

The constraints for the secret exponent apply because $\alpha^0$ meaning $x=0$ is $1$ and thereby fully insecure. If you use $p-1$, Fermat's little theorem applies and you get $\alpha^{p-1}\equiv 1\pmod p$ which is also trivially insecure. You can't get any value beyond $p-1$ because you can reduce those $\bmod (p-1)$ which allows you to reduce $p-1$ to $0$, $p$ to $1$ and so on.

As for the generator, you want to have one that generates a large group (via exponentiation) and this trivially excludes $1$ and $0$ which will you only ever give the sets $\{0\}$ and $\{1\}$ respectively. So they are a really bad choice for $\alpha$. You also can't chose $\alpha=p$ because you can then reduce this every time $\alpha=0$ as all operations are carried out $\bmod p$. Now what about $\alpha=p-1$ (the last edge case)? First you need to note that $p-1\equiv -1 \pmod p$ and if you exponentiate that you'll only get $(p-1)^x \equiv (-1)^x \equiv \pm 1 \pmod p$ which is the set $\{1,p-1\}$ and thereby a really bad choice.


Not quite, if all possible permutations are allowed.

There are $8! = 40320$ permutations over 3 bits; 15 bits of key allows you to specify $2^{15} = 32768$ of them; hence any mapping of 15 bits will necessarily $40320-32768 = 7552$ of permutations unexpressable.

It is doable if you don't allow every single permutation (e.g. allow only even permutations), or if you allow 16 bits of keying data.


Breaking keyed hash function with half-randomized input

If we consider the keyed hash function with $\ell=256$ keyspace than we can formalize as
$$H(k,m): \{0,1\}^{\ell} \times \{0,1\}^{256} \to \{0,1\}^{256}$$
Now assume that $H$ is a Cryptographically Secure keyed Hash function. That hash has pre-image, second pre-image, and collision resistance. The cryptographic strength of this hash functions is like the HMAC, the strength depends upon the size of the secret key that is used. Assuming that we have good enough key size from brute force $\ell > 128$ and the $H$ has no other weakness.
Now, assume that the attacker knows the key, in this case, it is just a usual hash function.

I think there is no way to find the 128-bit message. Am I right? Is the message safe in this case?

To find the actual message, the attacker needs to execute a pre-image attack. That has a cost of $\mathcal{O}(2^{256})$ since the attackers know the key. The pre-image attack can return an input $x$ such that $H(x) = target$ and the $x$ can be different than the 128-bit message or it can return many messages that one is the target.
The attacker has a better way since the input is 128-bit. They can search for the 128-bit. 128-bit is still beyond the search and considered secure. The collective power of Bitcoin miners can reach $\approx 2^{92}$ in a year, and one still needs $2^{36}$ years to reach a 128-bit search. In this calculation, the random 128-bit is discarded since it is not part of the security. If the random is considered secret (it shouldn't), then the attacker's job is just the pre-image.

Now output could be kind of randomized

We expect from the hash function to have avalanche criteria that is a bit change in the input should flip each output bit with 50% probability. The avalanche criteria is an important design criterion since if a few bit changes it may easier to find some collisions.
A special note: fixing a key to a keyed hash functions need a special analysis. Some keys can turn the hash function into a weak hash function. Since we don't know the hash function and the key we can not talk about this.


Can key-wrapping help to securely change passphrase used to generate encryption key?

Question1: How can be key-wrapping mechanism used when I forgot my password? (password is used to create wrapping key). I think that in this situation it cannot done and user's data are lost because I cannot unwrap original encrypt key so I cannot re-wrap original encrypt key. Am I right or wrong?

This is right of course, if you cannot recover the key required for unwrapping then you cannot unwrap.

  Question2: Is there some way / mechanism / technique how can I decrypt encrypted symmetric cipher key (AES) with two secret values? One value is derived from password / passphrase and second is from something as Apple's recovery key.

Yes, of course you can. This is quite often performed. It is even possible to require N out of M parts to form or decrypt the final key in certain protocols.

The recovery key size should of course be at least 32 bytes if you want to remain on the same security level as AES-256. Then again, using keys derived from a password will normally not provide 256 bit security either.


Why does AES ciphertext entropy always close to 8?

What you did in your entropy estimation is effectively modeled the process of selecting a random byte from the file, and computed the entropy that would be in that byte? You can do that (and, since you have the exact probability distribution, you could compute the Shannon entropy). However that would also answer your question - such a process would give you an 8 bit value; of course the entropy in that byte can't go beyond 8.

(The comment converted into an answer because, well, it appears to be the answer)


What are the differences between the elliptic curve equations?

All of these are answered by the SafeCurves project:

For twisted Edwards curves, $ax^2 + y^2 \equiv 1 + dx^2y^2 \pmod p$. Edwards curves are the special case a = 1.
Edwards curves can be converted to Montgomery form.Montgomery curves can be converted to Weierstrass form.Some, but not all, Weierstrass curves can be converted to Montgomery form.
The Montgomery ladder (applicable only to Edwards and Montgomery curves) is faster than standard weierstrass point multiplication methods.
the Montgomery ladder is constant-time, while the standard Weierstrass point multiplication methods are not.The Brier-Joye ladder allows constant-time point multiplication on Weierstrass curves, but is much slower than the standard point multiplication methods. The EdDSA signature scheme is only supported by twisted Edwards curves.


Are Merkle Dags really Dags in most cases?

It is certainly possible for a string to contain its own hash value, so it's even possible that $s_0 = s_1$.

And it's even possible to artificially construct functions that satisfy all the standard properties required of a cryptographic hash function (i.e. collision and first and second preimage resistance), but which hash an arbitrarily chosen string to a prefix of itself.  All you need to do take any standard secure cryptographic hash function and redefine its output for that single arbitrarily chosen input, as in fgrieu's answer to this related question.

However, no examples of such strings are known for any cryptographic hash function that is widely used and currently believed to be secure, such as SHA-2 or SHA-3.  Indeed, arguably, the ability to exhibit such a string would strongly suggest some kind of a weakness in the hash function, since finding such a string purely by brute force would be completely infeasible for any hash function with a reasonable output length (say, 256 bits or more).

Indeed, the same holds for longer cycles as well: as far as I know, for a random hash function $H$ with $n$-bit output, there's no way to find such cycles more efficiently than by using a generic cycle finding algorithm, all of which require at least $2^{n/2}$ evaluations of the hash function on average.

Finally, I should note that none of this necessarily has any relevance to whether or not Merkle DAGs or trees are well defined, as it's perfectly possible to define those structures in a way that allows two distinct nodes to have the same hash and/or the same children and/or content.  For example, the definition of a Merkle tree currently given on Wikipedia reads:

  [A] Merkle tree is a tree in which every leaf node is labelled with the hash of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes.

While this definition is rather terse, and glosses over some important details (some of which are addressed later on the page), the key point is that under this definition a Merkle tree would remain a tree even if all the nodes happened to have the same label, since the labels have no effect on the graph structure of the tree!

Of course, a secure implementation of a Merkle tree should not allow an attacker to feasibly construct two nodes with different children and/or contents but the same label, at least not on the same level of the tree, since swapping one such node for the other would then allow a forgery.  But even an insecure implementation that did allow that would still be well defined.

Conversely, even if you defined a Merkle tree (or DAG) in such a way that the connectivity of the tree was determined by the labels (i.e. such that a node $A$ was defined to be a child of node $B$ if and only if $B$'s label contained the hash of $A$'s label) then, as noted above, as long as you used a secure hash function with no known ways to find cycles faster than by brute force, you could still be practically certain that the resulting structure would indeed be acyclic.

A more serious conceptual issue with such a definition, of course, is that most non-leaf nodes of such trees would have an infinite — or at least a very, very large — number of possible children, simply because hash functions are non-injective and most hash values have infinitely many possible preimages, or nearly so.  Of course, for a secure hash function, finding most of those preimages should be computationally infeasible, but theoretically they still exist.

In practice, to put such a definition on a solid conceptual footing, you'd probably have to restrict the valid node labels to only those appearing in some kind of a global database of known strings indexed by their hash, and then explicitly require that it be infeasible for an attacker to find a string outside the database that shares a hash value with any string in the database.  Fortunately, this is a direct corollary of collision resistance (even assuming that the attacker can add strings to the database; otherwise second preimage resistance would be sufficient), and thus already (presumably) satisfied by any (presumably) secure cryptographic hash function.


Why are good passwords required if we use good hashing algorithms?

First of all, password strength rules like "at least 12 chars, numbers, signs, upper and lowercase" are actually counterproductive — they result in passwords that are only slightly harder to guess but significantly harder to remember, and worse, they also often end up also disallowing passphrases generated by actually secure methods like Diceware.

Their one arguable merit is that they disallow very common weak passwords like "password", "abc123" or "letmein".  Alas, preventing a user from choosing these weak but easy-to-remember passwords will typically just result in them choosing the simplest password that the system will accept, like "Password123!", which is still trivially guessable by any half decent password cracking tool (but now the user is much more likely to forget which punctuation symbol they used and whether they put it before or after the number).

(Another arguable historical rationale for such rules is that using a diverse selection of characters allows squeezing a little bit of extra entropy out of a short password, which could be relevant on systems that severely limit password length, like the old Unix DES-crypt scheme from the 1970s that truncated passwords to at most 8 characters.  But such archaic password hashing schemes are fundamentally unsafe anyway, and mixing a few punctuation characters into your password will not make them safe.  Still, this is likely one reason why such rules were originally introduced and popularized in the first place.)

Anyway, as far as it goes, your math it looks more or less reasonable to me: 3 billion seconds is about 95 years, so if testing a single password takes 3 seconds on a fast CPU, a password with about 30 bits of entropy (i.e. chosen uniformly at random from among $2^{30} \approx$ 1 billion possibilities) will take 95 CPU-years, which most attackers may consider too much effort.  That said, however:

Password cracking is an embarrassingly parallel task, so an attacker willing to dedicate 95 CPU cores to it will shorten the time to just one year.  With 5000 cores (which could be easily within reach of e.g. even a fairly small botnet or a server farm) it comes down to one week.

Also remember that processors still continue to get faster (and/or more parallel) and RAM prices still keep going down.  Not only does this mean that the time cost of cracking any specific password hash goes down over time, but you also cannot assume that all your users have the latest and greatest CPUs, whereas any decently motivated attacker probably does have access to those, or at least to something reasonably close.  Some of your users might be (at least occasionally) using 10 or 20 year old devices with slow CPUs and limited memory, and they'll want to be able to log in using them; an attacker with a botnet will have plenty of newer devices at their disposal.
Three seconds is already a rather awkwardly long time to wait for your password to be accepted.  For infrequent use it can be fine, but do you really want to wait that long every time you log in to a website or return to your workstation from a bathroom break?  I've seen one second listed as the maximum delay that most users are likely to find acceptable, and that's probably pushing it a bit.  Personally, I wouldn't aim much higher than 0.3 to 0.5 seconds.

If you'd like to try a quick experiment, count how many times you have to enter a password (even a prefilled one) or a PIN code per day.  Then try counting slowly ("1 mississippi, 2 mississippi, 3 mississippi") to three before pressing enter each time.  See how long it takes before you get tired of those pauses.
In any case, for authenticating to a remote server such as a website, even 0.3 seconds of key stretching per login is really only feasible if you can do the work on the client.  If you try to do the kind of slow and memory-intensive hashing you suggest on the server side, anyone can bring your server to its knees with a trivial denial-of-service attack just by having a bot try to log in with random usernames and passwords a couple of times a second.  Heck, you could probably do that even without a bot just by repeatedly clicking the login button.

With the Web Crypto API and/or WebAssembly implemented in modern browsers, it would be possible for a website to do key stretching on the client side.  I haven't seen any standards or widely used implementations for this, though, and while doable in principle, it has some nontrivial security and usability pitfalls that any custom implementation would need to be careful to avoid.  Also, it basically makes logging in impossible for users who cannot or will not run JavaScript, as any alternative fallback mechanism could also be abused by attackers.  So, at least for a while now, we're still mostly stuck with server-side password hashing.


Is AES-GCM length extension attack possible using authenticated decryption?

I did some more research and yes it does include both AD length and ciphertext length, so is not vulnerable to a length extension attack as length is part of GCM GHASH.

Based on NIST SP-800-38D (PDF) page 18 len(A) and len(C) are both part of the input into the GHASH function.

And double-checked this in an implementation gcm_finish method: both lengths are added to the hash at the very end.
https://github.com/polarssl/polarssl/blob/master/library/gcm.c


Problem with this authentication protocol

This is usually solved by creating a session key as part of the authentication process, then using authenticated encryption for the whole session. This is how e.g. TLS does it. Even if an attacker could hijack the connection, they do not have the session key so they cannot produce valid data.

The session key can be constructed in various ways. For example, a very simple, purely symmetric key protocol could have Alice generate a random key, encrypt the nonce using that key and the session key using the longer term key. The rest of the session would be encrypted and authenticated using the session key.

In practice it is a good idea to use something like Diffie-Hellman key exchange, since it gets you forward secrecy, among other things.


How to beat a substitution cipher when adding a pseudo-random number stream?

Phil Zimmermann here.  Yes, it was modulo addition of bytes from the pseudorandom number generator, and subtraction at the receiver end.  Essentially a stream cipher.  The fatal weakness was that I used a linear congruential generator, seeded by the key.  As weak as an LFSR.  I knew nothing at that time about the weakness of linear generators.  It was 1973.  I was clueless.  There were no crypto courses available in the university in that era.

This was not the last time I attempted home-grown crypto algorithms.  Later, in PGP version 1.0, I developed my own block cipher design called Bassomatic, a cautionary story I have told elsewhere.  From this humiliating experience I learned to only use extensively peer-reviewed algorithms.

-prz


Questions about proof of correct encryption in the Paillier cryptosystem

Revealing $r$ would then allow the verifier to prove to someone else (another verifier) that $c$ encodes $i$. The verifier could also prove other things knowing $r$ to a different verifier (any other proof using a paillier ciphertext, the corresponding plaintext, and the random value $r$).

With the ZKP, the verifier cannot prove anything to anyone else about that ciphertext. This seems like a useful property in some situations.

To answer your second question, assuming what I have said is the only side effect of revealing $r$, then your method would also allow the verifier to prove things about the sum to another verifier. That may or may not be an issue with your system. There could be other side effects that I am not aware of.


Is ECB mode secure if plaintexts are guaranteed to be unique?

Yes, this is one case where ECB mode is secure.

It can be shown to be secure trivially from the indistinguishability assumptions of AES; that AES with an unknown key cannot be distinguished from a random permutation.  If the plaintexts are all 16 bytes long, then in ECB mode, this directly means that the ECB mode encryption of those plaintexts are indistinguishable from random.

I'm sure MrNerdHair already knows this, but for those people who may be reading this later, lets make this a bit more explicit.  The assumptions that I am making are:

Every plaintext message is 16 bytes (either they're all 16 bytes, or they are all less than 16 bytes and become 16 bytes after padding).  If the message is longer (and so ECB mode does two separate encryptions), the attacker may be able to take advantage of the lack of interaction between those two blocks
Every plaintext message is distinct.  This matters because ECB mode encryption is determanistic, and so if we encrypt the same message twice, the ciphertexts will be exactly the same; this may be exploitable.


Limitations of boolean and arithmetic circuits

The question should be which functions can we build a small circuit to solve. Any function mapping a fixed number of bits to a fixed output can be represented as a boolean circuit. But it may be very large.
This brings is to a difficult topic with few lower bounds: https://en.m.wikipedia.org/wiki/Circuit_complexity


Are there recommended modes of operation for lightweight ciphers?

When using lightweight ciphers, the block size can make a huge difference to security. Fortunately, there has been a lot of work in recent years on tight bounds for modes of operations, and methods for going beyond the birthday bound. These modes are not stated as being especially for lightweight ciphers, so don't search for that. However, there is no doubt that when using lightweight ciphers with block sizes smaller than 128, then different modes of operation are needed (of course, depending on how much you want to encrypt). Here are three examples of work to look at (and the references therein):

CENC is Optimally Secure
New Blockcipher Modes of Operation with Beyond the Birthday Bound Security
Better Bounds for Block Cipher Modes of Operation via Nonce-Based Key Derivation


You asked a How do I question. You probably asked a Should I question. As in "Should I release a data set that reveals the distance between two strings where everything else is anonymized?" The answer is No unless you're making a crossword puzzle. (XKCD beat me to the joke for something similar. Your scenario is much more crossword-like however.)

Even if you found a scheme that didn't directly reveal individual letters, just having the information you get from string edit distances reveals a lot of information. Example: You have two records in a medical trial program with similar demographic data. You suspect "Bob Example Sr." and "Bob Example Jr." participated. Your two similar rows of data have “ “ “anonymized” ” ” (this needs triple scare quotes to triple scare you out of becoming responsible for publicizing poorly anonymized data) name records which are both 15 characters long and differ in one character. Start making guesses.

One could also build a weighted graph of dictionary words. (Where every node is a word and every pair of nodes is connected by an edge with weight equal to their edit distance.) For your idea you are hiding the labels of each node but not the edges or weights. One could make an informed guess at the values of the encrypted data by looking for similar sub-graphs in both the encrypted and dictionary-based graphs. Once you find one answer it becomes easier to guess the rest.

It is very difficult to design a system that anonymizes complex data sets. Otherwise intelligent people think they're outwitting hackers when they do things like hash email address, credit card info, or social security numbers. And that's the most obviously de-anonymizable scheme one can think of.

The most powerful tool to deanonymize data is to exploit the relations between data. If the purpose of your encryption is anonymization while maintaining properties in the original data then you're trying to do two things that are at odds with each other. It's a lot like deliberately encrypting with the same key/nonce pair even if you could find the perfect scheme.

Now to answer the "How do I [best stick a fork in an electrical socket"] part. I can think of three methods.

Store a table that relates pairs of records to their edit distance. This requires $O(n^2)$ space but is the least bad option. Omit the original string data or substitute it with randomly assigned ID numbers. You can't add new data to an annoymized database with this method.
If you want the Hamming distance between two strings, then use one substitution cipher for the first character of each string, another for the second, and so on. Breaking a substitution cipher is easy enough that it requires no knowledge of modern cryptography. (Or much knowledge at all beyond literacy.)
If you want Levenshtein distance then you use only one substitution cipher. This choice is also horribly insecure.

There may be better privacy-preserving methods than 2 and 3, but not 1. There may be way more complicated ways involving "multi-party secure distance computation, oblivious transform such as secure modular hashing, additive homomorphic encryption" but if any scheme leaks the data you say you want to preserve to a person who holds a copy of the supposedly anonymized data then it's no better at preserving privacy than 1.


Are there any specific requirements for the function $F$ in a Feistel cipher?

Luby and Rackoff published a famous article on that subject (SIAM Journal on Computing, 1988, Vol. 17, No. 2 : pp. 373-386 ). Namely, they showed that if the $F$ functions are pseudorandom, then four rounds are sufficient to achieve security.

There are subtle details, though:

Each round has its own $F$ function. We usually say that there is a single $F$ function indexed by the subkey for that round. In the Luby-Rackoff construction, the function for each round must be indistinguishable from a function taken at random, uniformly, among the set of possible functions which take an input as large as $R_i$ and produce an output as large as $L_i$; and that "random selection" must also hold between rounds (the round function for round 2 must be selected independently of the round function for round 1).
The security proof holds for balanced Feistel schemes ($L_i$ and $R_i$ have the same size).
If the block size is $n$ bits, then the security proof is valid up to $2^{n/2}$ elementary operations. So, if you want "proven" 128-bit security, the block cipher must use 256-bit blocks (or larger).

There is also the (technically unpublished) construction by Matt Blaze called Turtle: it is a four-round Feistel scheme for which each round function is itself a four-round Feistel scheme, recursively. Blaze links the security to an NP-complete problem, which is nifty, although it does not tell much about the security of the construction in practice (NP-completeness is about asymptotic behaviour; whether it applies on a given finite computational budget is a matter of guess and faith). Since Turtle was not formally published, it is a bit unclear whether the lack of cryptanalytic result is due to its inherent security, or lack of academic visibility.

A much more recent article from Morris, Rogaway and Stegers explores the security of unbalanced Feistel schemes where the "left part" ($L_i$) is a single bit. They show that, given enough rounds, one can get almost ultimate security, i.e. resilient against chosen ciphertext attacks up to $2^{n(1-1/r)}$ oracle requests, where $r$ is the number of rounds. This work is mostly useful in situation where we want small blocks. There again, the proof holds as long as the round functions are pseudorandom.

An empirical rule about Feistel ciphers is that, most of the time, complexity of attacks raises somewhat exponentially with the number of rounds. This holds as long as successive rounds are sufficiently dissimilar from each other; otherwise, you can have weaknesses due to slide attacks. For instance, one can say that if the best differential for the first half of the cipher has probability $P_1$, and the best differential for the second half has probability $P_2$, then the best differential for the whole cipher has probability at most $P_1 P_2$ -- but only if the two halves are independent of each other (i.e. use independent subkeys), which is an ideal but hard-to-get property.


Has there been any cryptanalysis of RC4-52?

Well, I have unaware of any specific analysis of RC4-52.  The closest thing I can think of is Cryptanalysis of RC4-like ciphers, which is an early paper which explores RC4.  Of particular interest would be section 5 (Tracking analysis), along with Table 4; that explores the obvious way to attack RC4-52.  Now, I suspect that it could be improved modestly (say, by attempting to search for a Fortuitous State, see section 5), however I suspect that won't gain you all that much unless you have huge amounts of keystream available).


Some devices I've been working with do indeed update biometric information.

The reasons is that there may be additional information:

acceptable fingerprint was scanned (required features are found), but the scan shows some area of finger not involved in previous scans.
some other additional information helping make more exact scans in the future


Is it possible to figure out it's value when $e$ is not bruteforce-able?

It depends.
First note that knowing you can easily factor $n$ given that you also know $\varphi(n)$ (2-prime case).
Next note that $\mathbb Z_n^*\cong\mathbb Z_p^*\times \mathbb Z_q^*$ (by the CRT), this means that doing component-wise operations on the pairs from the latter groups is a different way of writing an operation in the former group. Finally note that the bit-length of $p,q$ is about half of that of $n$ (usually).

Now that the preparation is through, the first thing to realize is that the given scenario is a standard discrete-logarithm problem with a composite modulus. Also note that the power of being able to choose the base shouldn't make the attacker stronger. Next thanks to the congruence and us knowing $p,q$ we can just map the problem to two smaller problems, finding $e$ given $x\mapsto x^e\bmod p$ and the same for $\bmod q$. Assuming the factors are reasonably small, a standard GNFS attack may work out, but with a standard RSA modulus of two primes of similar length resulting in a 2048-bit modulus this doesn't work.

Otherwise, this is a hard problem because it essentially constitutes a key-recovery attack on the Pohlig-Hellman cipher in a chosen-plaintext scenario.


Are there any tools to analyze cryptographic algorithms performance?

It is not given because it is assumed that you either know it anyway, if you deal with cryptographic algorithms, or you don't need it, because its complex and time consuming and only a few people in the world need it, and can properly read the result.
To test throughput (Mb/sec, same as processed data) you need a fast device to write to, usually hdd itself adds too much delay to measure this correctly. You could use ram filesystem for it, and write there. You didn't mention the OS, so I will assume linux.
You write a big file and measure the time it took
Knowing how big the file you've made and how much time it have taken, you can calculate the throughput, dividing file size by time taken.
You could use writing to /dev/null, but its hard to predict how much optimization OS will do, so I would offer to avoid this.
Key size is given in algorithm initialization, you cant start without giving this information. If Crypto++ hides this information from you, try to search for something else. Or look for default values. For AES its 16 bytes.
Same for block size. Same link shows that block size is 16 bytes for AES too. As with the previous case you set it up yourself, and many algorithms accept different versions of key size and block size. Those are given at the start by the user. Or are defaults, that can be found about the particular implementation, algorithm + program that make it work.
Power is hard to estimate because efficiency of devices differ dramatically. Even if you measure it for your device, it will be different for another device. Simplest way is to write a large file in RAM, delete it, write again, in a loop for hours till your laptop battery drains out. Then check how big your battery was.
Or try checking the power consumption of your flat on a power meter, but this is even less precise.
Proper method would use something like this
You could get a bit more precise result if you compare idle operating computer with computer that is doing your task. This way you automatically exclude all the parts that are not working for the cryptographic task, like a screen.
The cycles per byte is the most complex part. For this you actually need to read the code and see how many operations are done from start to finish, and then divide this amount of operations by the size of an output. If an algorithm took 17 operations like addition, xor and multiplication, and a device can do all of them in in one clock time, and output is 4 byte long, then the result is 17/4=4.25 cycles per byte. Keep in mind that modern CPU can operate on a very large words, 128bit (16byte), and that some operations can take a very long time, like exponentiation, that can take a 100 operations. You need to find the cost of each operation on a given machine. Usually it is 1 for addition, bit operations, multiplication, about 10 for division, sqrt, 100 for more complex operations like exponentiation, trigonometric functions for a modern CPU. Microcontrollers may only have fast addition. GPU may have fast division, but not bit operations. By fast I mean one cycle operation. So that in one clock step it will make one action like addition.
You may also be interested in checking how strong an algorithm is. This is done by reducing the key size and using a program that analyses the patterns in the output, TestU01 for example. Here is my favorite work on this topic, I like it for simplicity and visualisations mostly:
And this website in general. It allows to see how the cryptographic people think in general, what tools they use, what they value in an algorithm.
TLDR: you are asking about a lifetime worth of time spent collecting tools needed for a very complex task. I cant give you all of them. And there is no ready solution. Very few people need this.


Is there a preferred way/standard on how to transmit an initialization vector for AES encryption

The most common way to transmit an initialization vector is, indeed, to prepend it immediately before the ciphertext.

When you look at the original ciphermodes the first used IVs (CBC, CFB, OFB), the IV actually does function as a 'previous ciphertext block' for the very first actual ciphertext block; placing it immediately in front of the very first ciphertext block makes more sense than any other alternative.

Now, for newer modes (such a CTR), the IV is used in other ways internally.  However, the convention stuck.


Constructing a block-cipher from a hash function

It is possible to build a block cipher out of a great many things. If you want to use a hash function, the classic trick is to follow a Feistel structure, which is, incidentally, the same kind of structure than what DES uses.

The schematics on the Wikipedia page are quite clear; you would use the hash function for the "F" part, which combines one (sub)key and one half of the current block, to produce a value which is to be XORed with the other half of the current block. The beauty of the scheme is that the "F" function is always invoked in the same direction, both for encryption and for decryption. Therefore, it can be a one-way function, like a hash function.

Luby and Rackoff have demonstrated in 1988 that the Feistel scheme offers remarkable security with as little as four rounds, provided that the "F" function is "perfect" and that the cipher block size is big enough (to get the standard "128-bit security" out of the Luby-Rackoff proof, you need 256-bit blocks).

Of course, any concrete hash function cannot be really "perfect" (see for instance this answer) and there are a lot of subtle details which can destroy the security of the best thought cipher structure. As usual, you are strongly advised not to build your own crypto (unless you are quite clear with yourself that you do it for learning and not to actually protect any data of value).

Also, if you build such a cipher, you will probably notice that the resulting  performance is disappointing. With a secure hash function like SHA-256, you could expect an encryption bandwidth roughly 20 times lower than what AES would get you.