What does TLS 1.2 mean by SHA functions?

You're looking at just one small part of the protocol. TLS, like any other communication protocol combines several cryptographic primitives to provide communications security. The algorithms used to secure the communication channel are described by a cipher suite, which combines a key exchange method (usually some form of Diffie-Hellman), an authentication method (usually a signature algorithm), a symmetric authenticated encryption method, and a hash algorithm which is used together with the authentication method. (This is the format of typical TLS 1.2 cipher suites. There are several variations which I won't go into here. TLS 1.3 uses the same building blocks but encodes the choice differently.)
The TLS protocol starts with a handshake where the client and the server set up a secure channel. For signature-based cipher suites, which is the most common case, the client and the server conduct a Diffie-Hellman key exchange, which lets them obtain a shared secret (the premaster secret). They then derive secret keys for authenticated encryption from this shared secret. An adversary observing the exchange cannot obtain the shared secret. However, an active man-in-the-middle can open a connection with the client and another one with the server. To prevent that, the server calculates a hash of the data exchanged during the handshake and signs it with its private key. The client calculates the hash of the data that it has exchanged and verifies the signature with the server's public key. If the two sides were talking to each other, they have seen the same data, so the signature is correct. If the two sides were each talking to a man-in-the-middle, they have seen different data, so the signature is incorrect and the client aborts the connection.
There are many different methods for authenticated encryption. In the old days (up to TLS 1.2), encryption was done with either a block cipher in CBC mode or the stream cipher RC4, and authentication of the data was done with HMAC. Since TLS 1.2, it is possible and preferred to use a proper AEAD construction such as a block cipher in GCM or CCM mode, or some other authenticated cipher (ChaCha20+Poly1305).
I've left out many parts and variants. For a more detailed overview of TLS, read How does SSL/TLS work?
.


Is there a type of asymmetric and symmetric encryption that's fairly easy to crack?

Assuming that the root source of secrecy is only an average password, then the choice of cipher does not matter so much. Especially if the key derivation step is not handled well.

Direct your computing power to:

Guess a password
Derive key material using the system parameters
Use that key to attempt decryption of the ciphertext

Authenticated encryption provides an oracle for verifying the key guess

Which system?

This seems like a nice candidate. It uses PBKDF2, which is better than nothing, but it isn't as resource intensive as bcrypt/scrypt/Argon2. It's implemented in python so it shouldn't be too hard to make any necessary modifications.

You can tune the iterations so that it is breakable with your given amount of computing power. As long as the target password isn't too complex, it should be feasible.

How to guess passwords?

There is plenty of software out there already. Some of it will even have nice features like organized word lists, including commonly used passwords and passwords from real breaches.

Depending on how handy you are as a programmer, it may or may not be easy to write your own basic password cracker.


What cryptography primitives can help me (generate unforgeable tag)?

Assuming that all the $m$ values are the same, then about the only thing to do with the precise verification procedure you specified is to set:

$$t_i = c \cdot {a'_i}^{-1}$$

for some secret constant $c$ (which needs to be the same for every tag).

This would appear to work (and any value of $c$ would work)... until some $a'_j$ value is leaked; then, the attacker could rederive $c$, and thus recover all the $a'_i$ values from the corresponding $t_i$ values.


This can be seen as a particular case of secure two-party computation, where one party has the (encrypted) inputs, and the other has the decryption key. There is no specific name for the functionality you are looking for, as it is just a particular functionality that one can want to realize in the framework of two-party computation.

So, I think you're looking for a two-party computation protocol realizing the following functionality:

Alice has input $E(a),E(b)$, where $E$ is some encryption scheme (I guess that in the scenario you have in mind, it's an FHE), and Bob has the decryption key of this FHE scheme. You want to realize the functionality that returns $E(a/b)$ to Alice, and nothing to Bob.

(note that even a perfectly secure realization of this functionality will at least leak whether $b = 0$, so you have to make sure this is not an issue for you in the larger protocol you want to use this subprotocol in).

As for how to implement it: if you're using an FHE scheme and just want to avoid doing the expensive division, it's super easy. Just let Alice homomorphically multiply $b$ by some $r$, and randomize the ciphertext: she gets $E(rb)$ and sends that to Bob. Bob decrypts, gets $rb$, computes $(rb)^{-1}$, encrypts, sends back. Alice gets $E((rb)^{-1})$, and homomorphically multiplies with $r$ and $E(a)$ to get $E(a\cdot b^{-1})$.

I suspect from your comments, however, that you are interested in approximate division of floats, and not just computation of $E(a\cdot b^{-1})$. Is it the case? If so, you will likely need a much more complex and interactive protocol.


In a disk cipher like the M-94, each key corresponds to a permutation of the cipher disks.  Thus, with $n$ disks, there are $n! = 1 \times 2 \times 3 \times \dots \times n$ distinct possible keys.

(It's technically possible for some of these keys to be equivalent, e.g. if two of the disks are identical.  But this is extremely unlikely if the letters on each disk are ordered randomly.)

Note that enumerating the keyspace by brute force is not the most efficient way to attack a disk cipher (and thus the size of the keyspace is not a meaningful indicator of the strength of the cipher), regardless of whether the attacker knows the alphabets on the disks or not.

Rather, a typical cryptanalytic approach would exploit either known or guessed plaintext, or simply the fact that consecutive letters in English text are highly correlated, and in particular, that certain words and phrases like "THE" or "AND" occur far more often than one would expect by chance.

For example, if the ciphertext begins with the letters "XYZ", and if we know (or can guess) that the first word of the plaintext might be "THE" and that the first cipher disk might be disk 1, then it's easy enough to locate the letters "X" and "T" on disk 1 and see which other disks have "Y"/"H" and "Z"/"E" at the corresponding positions.  If we find two such disks — say, disks 4 and 7 — then we can guess with a pretty good confidence that the first three disks in the key may be 1, 4 and 7, and proceed further from there; if we don't, then one of our guesses must be wrong, and we may e.g. try another disk for the first letter and see if that yields a solution.

(The attack described above assumes that the alphabets on the disks are known.  If they're not, a similar attack can still be carried out, based on repeating patterns in the ciphertext where the same word at the same position just happened to be encrypted with the same row, although it will require a lot more ciphertext and effort to succeed.  Even so, such an attack is still a lot more efficient than brute force enumeration of all the possible alphabets on each disk.)


Is a RSA-signature of some identifying data a safe way to implement a license key?

That is not a bad method of doing a license key; an attacker would certainly be unable to generate a signature that would validate with his computer's window product key.

On the other hand, this approach may be overkill. The easiest way to attack this system would be to modify the program to skip (or ignore) the signature validation; hackers have both the experience and the tooling to do this fairly easily.  I don't believe that there are any easily implemented license key approaches that make that attack more difficult; however, there are certainly other approaches that would be easier to implement.

Since you asked for cryptographical advice, here is some:

If you do use this approach, you might as well make sure you get the details correct; you use a known-good padding scheme (say one of the ones listed in PKCS #1).
You ask whether the window product key is long enough.  The answer is "Yes, it is".  Actually, the length of what you sign is not important to the security of the signature method; it just needs to be long enough to be unique.


Since noone has written down an answer, I'll give it a go.

There are two important parts of your (or of any) security definitions:

An adversary $\mathcal{A}$, with bounded computational power;
A bound ${\tt negl}(x)$ on the advantage of $\mathcal{A}$.

These lead to two important observations:

The more power we give $\mathcal{A}$, the stronger our security notion;
The tighter ${\tt negl}(x)$, the stronger our security notion.

Ideally, you'd give $\mathcal{A}$ unlimited power, and show that he can achieve 0 advantage.

What does this look like in your definitions? Let's first consider $\mathcal{A}$. In (1), your adversary has polynomial computing power. In (2), your adversary has sub-exponential computational power. From this perspective, (2) makes a weaker assumption on the adversary, and thus would provide a stronger security guarantee than (1).

But as mentioned, the security does not only depend on the adversary. In (1), the function ${\tt negl}_1(x)=1/{\tt subexp}(x)$. In (2), there is no definition of ${\tt negl}_2$. I'd say there are two options:

${\tt negl}_2(x)\leq{\tt negl}_1(x)$. Then (2) makes a weaker assumption on the adversary and has a tighter bound on the advantage. Thus (2) gives a stronger security guarantee.
${\tt negl}_2(x)\gt{\tt negl}_1(x)$. Now (2) makes a weaker assumption on the adversary, but (1) has a tighter bound on the advantage. In this case I'd say neither is better. It's basically saying "if we give the adversary more power, he can get more advantage". It would probably depend on context which of the two is applicable.

Edit: I may have misunderstood your question, if you mean (2) to have negligible advantage according to the usual definition. In that case the above is probably obvious to you, and does not help at all towards your question. I guess I'll just leave it in case it helps someone else..


Of course not; 8 bits have a maximum of 8 bits of entropy.  There does not exist a probability distribution over the 256 possible values of those 8 bits that gives an entropy value of more than 8.

What this means is that your function can have more entropy on the input than the output.  This is not uncommon, and typically happens if you have a function with fewer possible outputs than inputs (the only exception is if the probability distribution that the input occurs has some inputs with zero probability).


eSTREAM competition has 2 profile:software and hardware,and the goal of hardware profile was to design a stream cipher that it should be hardware-optimized,and the final candidates were grain v1 and Trivium and MICKEY v2.a comparison of hardware performance of Grain,trivium and MICHEY is on the below image:


AES GCM symmetric encryption of data at rest in c#, ciphertext much longer than plaintext

If you go through the math, it appears that exactly the expected amount of ciphertext expansion is happening.  Here's what's happening:

The GCM takes the plaintext as a byte string of size N, and generates a ciphertext which is a byte string of size N+28, where 12 of the 28 is the nonce, and the other 16 is the authentication tag.
Then, that octet string undergoes a base-64 encoding, which converts 3 bytes into 4 printable characters; this gives an average ciphertext expansion of a factor of 4/3.

In the first case, you had a plaintext of 7 bytes; after encryption, that gives you a ciphertext of 35 bytes; the base-64 encoding of these 35 bytes would be expected to be 47 bytes long, which is exactly what you see.

In the second case, you had a plaintext of 46 bytes (assuming there's a trailing space to the string you gave); after encryption, that gives you a ciphertext of 74 bytes; the base-64 encoding is then 99 bytes, which is exactly what you see.

Now, you ask how you should fix this issue.  Well, the transform is working as designed; what is the issue?  If the issue was that you were concerned that something wasn't working properly, well, everything appears to be correct.  If the issue was that the ciphertext was too long for your application, well, you'd need to consider how to trim it.  Here are some easy ways:

Do you really need the output to be printable?  Well, I see you put the 'database' tag on the question; are you encrypting a database field?  If so, can the database store arbitrary bytes, or is it restricted only to printable strings?  If it can store arbitrary bytes, then you can get rid of a good part of the overhead simply by not base-64 encoding the text.  If you do, well, if you're desperate, there are some more aggressive encoding methods (which use more characters in their outputs); going to one of those would save you some small amount.


Diffie-Hellman private key recover with non-prime modulus

We start by finding the factorization of $p$ as $\prod p_i$; then find the $x_i$ with $g^{x_i}\equiv y\pmod{p_i}$ using an auxiliary algorithm to solve the DLP, perhaps Pollard's rho and/or Pohlig-Helman.

I'll assume that the $p_i$ are distinct, which was the case in the original question. They thus are coprime, and by the Chinese Remainder Theorem $g^x\equiv y\pmod p$ is equivalent to $\forall i, g^x\equiv y\pmod{p_i}$.

Fermat's little theorem tells us that $g^{p_i-1}\equiv1\pmod{p_i}$, since $p_i$ is a prime not dividing $g$. Therefore, $g^x\equiv g^{x\bmod(p_i-1)}\pmod{p_i}$. Therefore it is sufficient to find $x$ such that $\forall i,x\equiv x_i\pmod{p_i-1}$ (see final section for a better alternative).

Problem is, the moduli $m_i=p_i-1$ are not coprime: for a start, they all are divisible by $2$. That prevents a different use of the regular CRT to find $x$. We need to reduce the $m_i$ in order to make them coprime, while leaving their Least Common Multiple unchanged.

Assuming that we can fully factor the $m_i$: we collect every prime $q_j$ in these factorizations, and find it's maximal multiplicity $k_j$ (that is the maximal $k_j$ so that $q_j^{k_j}$ divides at least one of the $m_i$). Then for each $q_j$, we select one (of possibly several) $m_i$ that $q_j^{k_j}$ divides, and we divide each other $m_i$ by $q_j$ as many times as possible.
Note 1: Each time we divide an $m_i$ by $q_j^{k_{j,i}}$, we can check that $x_i\equiv x_j\pmod{q_j^{k_{k,j}}}$, and otherwise conclude that there is no solution.
Note 2: We can avoid full factorization of the $m_i$ and use Greatest Common Divisor computations, but that's slightly involved; see this.

If $x\equiv x_i\pmod{p_i-1}$, then $x\equiv x_i\pmod{m_i}$ holds for the reduced $m_i$. The converse holds if we made the checks in note 1. We can now find a suitable $x$ using the regular CRT, requiring coprime $m_i$. We do not need to recompute the $x_i$, but we can reduce them modulo $m_i$.

If we did not perform the checks in note 1, we need a final check that $g^x\equiv y\pmod p$.

Another issue is that $x\equiv x_i\pmod{p_i-1}$ is a sufficient, but not necessary condition for $g^x\equiv g^{x_i}\pmod{p_i}$ to hold. Thus, the CRT applied as above can find an $x$ that's needlessly larger than needed. A solution to this is to initialize $m_i$ with the order of $g$ modulo $p_i$, that is the smallest positive $m_i$ with $g^{m_i}\equiv1\pmod{p_i}$. That's some divisor of $p_i-1$, not always $p_i-1$ itself.


Yes, we can change the irreducible polynomial of AES to another irreducible polynomial. In doing so we have to implement a change of basis or change the polynomial for the S-Box, this may effect the security. Moreover research had been done on how to enhance the security of AES by changing the irreducible polynomial. See this paper for detailed discussion.

Hope this helps.


Why are the session keys in DHKE for different values of 'a' the same?

Since $\gcd(2,467)=1$, one can observe using Fermat's little theorem  that $4^{233}\pmod{467}=2^{466}\pmod{467}=1$.

Thus,
$$g^{a_1}=4^{400}=4^{233+167}\equiv\underbrace{1\cdot4^{167}}_{=g^{a_2}}\pmod{467}=89.$$

This results into identical session keys (shared secrets) $S=(g^a)^b=89^{134}\equiv161\pmod{467}$.


How to construct the blind factors in practice?

Blinding technics are well know now to defeat most attacks against SCA.
You need a random number generator (True or Pseudo) to generate unpredictable random $r_i$.
Additionnal precautions against Zero Attacks values can alo be taken.
Try this: $m_0=y_0 \times r_0 \; + \; r_1 \times p \; mod \;(r_2 \times p)$


Why does DSA require that a new $k$ be chosen and the algorithm restarted if $s=0$?

The algorithm needs to be restarted because the private key $x$ can be obtained when $s=0$.
From:

$s=[k^{-1}( H(M) + xr)] \mod q$

We can solve for $x$ and get:

$x=\frac{-H(M)}{r} \mod q$


Does exposing algorithm, key size and IV weaken the security?

No cryptography worth its salt should become less secure because its inner workings are known. It is usually assumed that the adversary has all that information when doing security proofs (Kerchoff's principle/Shannon's maxim).

In your particular case the tool is using pretty standard crypto (AES-CBC-256) so you don't need to worry about exposing its details.

As some of the other comments point out, the tool you're using seems to have disabled the MAC (message authentication code), which opens it up to attacks in which the attacker could modify the ciphertext of a given file in deterministic ways such that you would decrypt a message of his/her choosing. I would recommend you enable it.

Another thing to note about file encryption is that the ciphertext (or the AAD -Additional Authenticated Data- if you were using authenticated encryption such as GCM) should contain the filename as well. Otherwise an attacker can swap the ciphertext of a file for another one you also encrypted.

Now, you specifically ask if this helps an attacker focus his attacks. I guess the answer is yes, if there were attacks against a particular ciphersuite, knowing that it is the one being used will facilitate the attackers task. On the other hand, if the attacker can interact with the system he/she will most likely figure it out given enough time. Or they could just throw all known attacks at it. In summary, there is nothing to gain by hiding this type of information.


Does AES specify error messages when using the wrong password to decrypt?

AES in general does not specify that it should return a bad padding message. In fact, AES in general says nothing about padding. Padding schemes are external to AES. Therefore, the message you are getting is .Net specific.

That said, be careful with these messages, as they can lead to a padding oracle attack.


"If PGP and GPG both follow the OpenPGP standard, are they 100% compatible in all use cases?"

No, they are not 100% compatible in all use cases, because — depending on the PGP version — there are known interoperability problems.

The GNUPG FAQ answers this question quite well:

  Is GnuPG compatible with PGP?

  In general, yes. GnuPG and newer PGP releases should be implementing the OpenPGP standard. But there are some interoperability problems. See question How can I encrypt a message with GnuPG so that PGP is able to decrypt it? for details.

For your convenience, I'll also quote that linked Q&A:

  How can I encrypt a message with GnuPG so that PGP is able to decrypt it?

  It depends on the PGP version.

  PGP 2.x

  You can't do that because PGP 2.x normally uses IDEA which is not supported by GnuPG as it is patented (see How do I include support for RSA and IDEA?), but if you have a modified version of PGP you can try this:

$ gpg --rfc1991 --cipher-algo 3des ...

  Please don't pipe the data to encrypt to gpg but provide it using a filename; otherwise, PGP 2 will not be able to handle it.

  As for conventional encryption, you can't do this for PGP 2.
  PGP 5.x and higher

  You need to provide two additional options:

--compress-algo 1 --cipher-algo cast5

  You may also use "3des" instead of "cast5", and "blowfish" does not work with all versions of PGP 5. You may also want to put:

compress-algo 1

  into your ~/.gnupg/options file — this does not affect normal GnuPG operation.

  This applies to conventional encryption as well.

I think that pretty much answers your question.


What information should I send along with an AES ciphertext and is there any standard to do that?

What you are looking for is a definition of PEM, privacy enhanced mail. Obviously PEM is not just used for mail anymore. The definition of the header lines seems to be best described by section 4.6: "Summary of Encapsulated Header Fields" of RFC 1421: "Privacy Enhancement for Internet Electronic Mail: Part I: Message Encryption and Authentication Procedures". Obviously for PGP specific header fields you'll have to take a look at the OpenPGP format, specifically the section about ASCII armor.

  Then, i would like to use a comment like the one showed above to store my ciphered messages as plaintext. Assuming i want to do that for a message ciphered using AES, which informations should i store ?

That depends on the scheme you've chosen. For transport security the minimum would be the IV, the ciphertext and an authentication tag over both.

  Should i store the AES mode used for encryption ?

That depends. You could store a protocol version instead which determines which mode is used. You should not just store the mode without authentication and then proceed to process the message based on the header fields. That would give an attacker to decide which operation is performed on the receiving side. You need to keep control over what is performed on the receiving side.

  Should i store the AES implementation i used ?

No, the implementation of the block cipher should be irrelevant if you've decided upon a well defined protocol.

You could store a version of the software implementation of a protocol. In that case you may be able to work around possible bugs within the implementation. I've seen quite a few instances where the implementation of PGP did matter.

  Should i store the initialization vector ?

Yes, unless you've got ways of establishing the IV out-of-band (e.g. an operation over a message counter included in a message counter, or a counter kept in sync at both sides). If unsure include a random IV of sufficient size.

  Should i try to be compliant to some standards while storing these informations ?

It's strongly advisable to keep to well known container formats such as CMS or the already named OpenPGP yes.


Piggyback on Bitcoin for independent data verification?

I think what you might be looking for is an append-only data structure for example "Balloon: A Forward-Secure Append-Only Persistent Authenticated Data Structure". A similar concept is used for certificate transparency as specified in RFC6962

Edit: If you definitely want to use the bitcoin blockchain you should look at this or this.
Somebody actually has asked this question before.
A PoC implementation can be found here.


Would Triple DES-X with 7 keys be much slower than standard Triple DES?

Well, there's a fairly obvious CPA attack that uses circa $2^{34}$ or so chosen plaintexts, and about $2^{120}$ trial DES operations. Because of that, the cryptographical strength is not significantly higher than standard 3DES.
As for code size and memory size, it'd certainly be larger than standard 3DES (you do more, and have more keying material lying around) - but it's hard to make a guess as to how much.
The scheme would likely be somewhat slower than 3DES. For 3DES, you can omit the intermediate IP/FP permutations between DES operations. In the scheme you've defined you would have to have them in there, and you would have to perform the columnar transposition as well. Now, it looks plausible that you could combine the FP/transpose/IP between DES operations into a single operation, which would reduce the cost somewhat, but it still wouldn't be as cheap as omitting them entirely.
On the plus side, this is effectively a 128 bit block cipher, so you do avoid the vulnerabilities that come with a 64 bit block size.


What does «CRC32C (alias Castagnoli) is better than CRC32B in detecting errors» exactly means?

Multiple metrics are used in the original article. One is: when we restrict to messages of equal length differing by at most some low number of bits (e.g. 4 bit), CRC32C gives certainty of error detection up to a larger message length than CRC32 does. This is confirmed independently. Variations consider the probability of error detection for messages slightly above the threshold of perfect detection on either the message length, or number of bits in error.

I'm not sure that the 66 vs 44 collisions found in the question is statistically significant, or the cause of that if it is significant.


How to determine the layers of a circuit?

Given a circuit for f, how can we optimize to get a "shallower" circuit for the same f? Are there any tools/algorithms available for this purpose?

Researchers have already identified this is a relevant problem for MPC and FHE, where low-depth circuits make a big performance difference.
Some works in this direction include [BDKK+18] and [BHWK16], and digging through their reference will reveal more work in that direction.

Some of the techniques in this area include adapting some optimization tools from circuit synthesis in the electrical engineering domain, and there are some other hand-crafted optimizations as well.

  Suppose the circuit for f if given as a list of gates, where each gate points to the gate or gates corresponding to its input. How can we determine the layers of the circuit from such representation? Are there any tools/algorithms for this as well?

I know of two ways of achieving this.

Greedy algorithm

One that is very intuitive works as follows, at a high level.
Take the input nodes and compute all the addition gates you can compute from these nodes without stumbling upon a multiplication gate.
Then compute the multiplication gates that only depend on any of the gates found above (including the input gates).
These gates have depth 1.

Then compute all the addition gates that depend on any of all the previous gates, and then compute the multiplication gates that depend only on the gates found up to this point.
These have depth 2.
This iteration is continued until all gates have been processed.

Using dynamic programming

This approach is considered in [KSS13].
To each edge $v_{ij}$ going from gate $g_i$ to gate $g_j$, assign a weight of $0$ if $g_j$ is an addition gate, and assign a weight of $-1$ if $g_j$ is a multiplication gate.
Then, it is easy to see that the depth of a gate becomes the (negative of the) shortest distance from the gate to any of the input nodes.
This can be computed via dynamic programming algorithms like Dijkstra algorithm.

[BDKK+18] HyCC: Compilation of Hybrid Protocols for Practical Secure Computation (link)
[BHWK16] Compiling Low Depth Circuits for Practical Secure Computation (link)
[KSS13] An architecture for practical actively secure MPC with dishonest majority (link)


Modular reduction for NIST prime P256-- understanding the data

In the document the P-256 parameters describe the curve P-256 on which you want to perform the operations. Traditionally a curve is represented in Weierstrass-form as the set of points for which

$$y^2\equiv x^3 + ax+b \pmod p$$

holds. Where $p$ is the prime defining the field for the operation and $a$ and $b$ define the shape of the curve. A point on the curve is a pair $(x,y)$ for which the above equation holds.

Now in order for elliptic curves to be actually useful, we want to perform operations on them. Usually this addition of two points, like $R=S+T$ with $R,S,T$ being curve points and we want to double points and thereby allow for fast exponentiation using the repeated square and multiply algorithm (although in practice you'd be more clever to avoid timing attacks). Doubling is usually denoted as $R=2S$ with $R,S$ being points on the curve.

Now to the basics on how to actually double and add two points. This is indeed described in the linked document. For reasons of efficiency, usually a third component for the points is defined $z$. If you have a point given only as $(x,y)$, define $z=1$. For practical applications I strongly suggest to simply follow the algorithms given in the document.

For verification you can use the below equations and the test vectors from the document. Note that for each section of the samples the parameters of that section need to be used.

To add two points $R=(x_R,y_R,z_R)$ and $S=(x_S,y_S,z_S)$ you can use the following equations to get $T=(x_T,y_T,z_T)$:
$$u=y_R\cdot z_S - y_S\cdot z_R\bmod p$$
$$v=x_R\cdot z_S - x_S\cdot z_R\bmod p$$
$$w=u^2\cdot z_R \cdot z_S - v^3 - 2v^2 x_S\cdot z_R\bmod p$$
$$x_T=vc \bmod p$$
$$y_T=u(v^2x_S\cdot z_R-w)-v^3y_S\cdot z_R \bmod p$$
$$z_T=z_S\cdot z_R v^3 \bmod p$$

And finally you calculate the modular inverse of $z_T$ and calculate the affine coordinates of the resulting points as $x_T=x_T\cdot z_T^{-1} \bmod p$ and $y_T=y_T\cdot z_T^{-1} \bmod p$ giving you again the "classical representation".

This is "only" the addition law for two distinct points. Doubling is similarly complicated and should be implemented by strictly following the specified algorithms.
If you really want to learn more about EC crypto you may find more answers in the Handbook of Elliptic and Hyperelliptic Cruve Cryptography. The above algorithm is taken from Introduction to modern Cryptography (Second edition).


Why still we are using classical key exchange rather than quantum idea

Well, not everybody is willing to put an optical line from each person to another or install the hardware components to do the quantum computing, for one. You cannot just send the information over the internet protocol or even electrical wiring.

QC key distribution is commonly used by large organizations and governments that want to distribute secret keys relatively often (otherwise you could just send it by courier).

Besides, without fully functional quantum computers for analysis, DH is still considered secure, at least when the proper authentication and verification procedures are in place.

Note that QC is no panacea either; you could for instance try and retrieve information from the equipment or find other holes in the way the QC is actually implemented. More info in section 4 & 5 here.


Is the warning given by chrome warranted?

There are four issues (basically all you can get at once I think) going on with your connection to this site which is why Chrome warns you.

The first one is quite easy to spot: The usage of SHA-1 for the certificate signature. SHA-1 is generally considered deprecated and should not be used for scenarios where collision resistance is required, like certificate hashing. A well-funded attacker may be able to create two valid certificates having the exact same SHA-1 hash, it's only a matter of time until someone presents the first such collision to us (maybe some agency?).

And to actually answer this part of the question: Yes, SHA-1 has been considered obsolete for quite some time now, but people tend not to move away from things until there's a real threat, although many CAs need do the transition. The second reason for why they may still use is that they got a 4-year certificate back in 2012 (and those tend to be expensive) and deprecating SHA-1 wasn't a thing back then as much as it is today (Google's post is from 2014).

The second warning you observe is the lack of certificate transparency. Certificate transparency is Google's action against fraudelent CAs issuing certificates to people who shouldn't be able to get those certificates. They do this by "forcing" everyone to publish the issued certificates into a set of logs so everyone can identify if his domain is subject to such attacks. This is still in the early stages and not by-default supported by many CAs. It will only remove the EV bar if you're using Chrome.

The third issue on this warning page is mixed content. This means parts of the page are served over unencrypted connections and may pose a security threat to you as they can be observed and altered by anyone in between you and the server. This may cause a noticable warning.

The fourth issue is the use of AES-CBC + HMAC-SHA1. Note that indeed HMAC-SHA1 is still safe and will be for quite some time. Note further that there indeed exists security proofs for the way TLS handles CBC+HMAC.

However, CBC failed quite a bit in the past (POODLE and others) and even some TLS implementations were vulnerable. Furthermore CBC has quite severe requirements on the IVs used for each packet (they need to be unpredictable as opposed to be "just" unique). And of course it's harder to correctly use CBC+HMAC than it is to just an AEAD scheme (such as GCM) as you have to take care of a lot more stuff (keys, call the MAC in the right place, generate correct IVs). The last point on TLS' CBC+HMAC is that the security proof is considered "bad". TLS uses MAC-then-Encrypt when using CBC which doesn't have a security proof as generic as Encrypt-then-MAC has making it potentially more error-prone. It is for these reasons Chrome considers connections made using CBC as obsolete and why only AEAD modes are allowed for TLS v1.3.

TL;DR: SHA-1 is indeed deprecated but getting rid of it takes time and AES-CBC+HMAC-SHA1 has provable security but is considered "obsolete" and error-prone for quite some reasons so Chrome issues you the warnings.


Proof by reduction definition in "Serious Cryptography": Cipher reduced to hardness problem or other way around?

The definitions come from Turing Reduction of Wikipedia

  In computability theory, a Turing reduction (also known as a Cook reduction) from a problem A to a problem B, is a reduction which solves A, assuming the solution to B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve A if it had available to it a subroutine for solving B. More formally, a Turing reduction is a function computable by an oracle machine with an oracle for B. Turing reductions can be applied to both decision problems and function problems.

which can be simplified as $A$ is reduced to $B$;

If $A \leq B$ then, if you were given a subroutine for $B$ you could solve $A$.
This can be also mean that $A$ is no harder than $B$.

  I am wondering if this is the right direction. Assume we reduce the problem of breaking a cipher $P$ to some problem $X$, $P \leq_m^p X $, as suggested by the book (if I understand correctly). Then if we have a polynomial-time algorithm for $X$, we also have a polynomial algorithm for $P$. But this does not guarantee that if no polynomial algorithm for $X$ exists, there should be no polynomial-time algorithm for breaking $P$. In fact, there could still be a polynomial-time algorithm breaking $P$ in some way unrelated to problem $X$.

So we have $P \leq X$, which means we use $X$ as a subroutine and $P$ is not harder than $X$.

Yes, the reduction doesn't say about a polynomial-time algorithm exists or not. If one can prove that there is no polynomial-time algorithm for $X$ than this doesn't mean that there is no for $P$. Because the reduction is just a useful upper bound.

If there is a polynomial-time algorithm for $P$ this can be used to solve $X$ if one can show that $X \leq P$. Otherwise, as stated in the second bullet, the reduction provides only the upper bound.

  So shouldn't the reduction be the other way around $X \leq_m^p P$. That is, if we can break $P$ in polynomial time, we can also solve $X$ in polynomial time?

Not exactly, the reduction gives the upper bound. To use a polynomial-time algorithm for $P$ to solve $X$ one needs to show that $X \leq P$.

  This way, if $X$ is hard (not polynomial-time solvable), then by contraposition $P$ must also be hard, thus $P$ is at least as hard as X?
  What am I missing here?

Assuming that one showed a reduction of $X \leq P$, then the information we have $X$ is no harder than $P$ with $P$ is solvable in polynomial-time. If you show that $X$ is hard ( assuming NP-hard here) then one must look at either the reduction or the hardness of solving $P$ again.


Is there any benefit from using SHA-512 over SHA-256 when AES just truncates it anyway?

SHA-512 has both a larger internal state and a higher number of rounds than SHA-256 - which means that it provides a higher bit strength. Somewhat surprisingly it may also outperform SHA-256, as it uses 64 bit word size, which works best on 64 bit processors. You can see a good comparison table on Wikipedia

If less bits are required from SHA-512 then they are generally just taken from the left of the output (it doesn't matter which bits are used, this is just convention). There are also specialized constructs such as SHA-512/256 that use different initial values. This should be used in case the leakage of a partial hash is a problem within the specific protocol.

That said there are no attacks on SHA-256 that come close to breaking that particular algorithm, so it can still be used with some kind of confidence.

There is no such thing as a SHA-256 or SHA-512 key. SHA-2 may be used to derive keys though, for instance using HKDF. For key derivation it is best to use the hash as part of a HMAC function to create a PRF.

As deviantfan commented, CBC requires an IV. The additional output of the SHA-512 function could be used to deliver those additional 128 bits.

For GPG specifically, RFC 4880: OpenPGP Message Format specifies in section 3.7.1.1: Simple S2K:

  If the hash size is greater than the session key size, the high-order (leftmost) octets of the hash are used as the key.

This is also the method used for Salted S2K and Iterated and Salted S2K as those expand the Simple S2K function.

Note that there is a specialized SHA-512 version called SHA-512/256 standardized by NIST, which let you use a version of SHA-512 with reduced output. It uses different constants which could fend of some attacks as the start of a hash may tell an attacker something about the full hash. Obviously it therefore produces different output than (the leftmost bytes of) SHA-512. SHA-512/256 should be used instead of SHA-512 in new protocols if your target platforms support it.


Explain Fischlin's Fiat-Shamir like transformation

I think I got it.
The point, in short, is that you require multiple proofs (commit_i,challenge_i,response_i), where each proof's validity depends on all the first messages commit; i.e., on COMMIT=(commit_1,..,commit_k).
So if the probability of a good proof is 1/l,
if you try to get a good sequence (proof_1,..,proof_k) by complete random sampling (from the space of l-tuples of correct proofs), it will take you in expectation 1/l^k.
But if you fix COMMIT, and try different values of challenge_i,response_i,
it will take you in expectation lk tries.
Taking l to be polynomial and k super-constrant, you can get the first to be super polynomial but not the second.


Relationship between existence of OWFs and OWPs

Short answer: "No".

The standard way to establish a statement of the form if a primitive $B$ exists then another primitive $A$ also exists is through a black-box reduction. This involves two steps:

Constructing an instance $\alpha$ of $A$ given black-box access to an instance $\beta$ of $B$ --- this is denoted by $\alpha^\beta$, where $\beta$ in the superscript refers to $\alpha$ having only oracle-access to $\beta$; and
Showing that $\alpha^\beta$ is hard to break assuming $\beta$ is --- this, in turn, is accomplished through a reduction algorithm $\mathcal{B}$ that breaks $\beta$ given an adversary $\mathcal{A}$ that breaks $\alpha$. ($\mathcal{B}$ only has black-box access to $\mathcal{A}$.)

Primitive $A$ is said to be black-box-reduced to primitive $B$. (Henceforth, by reduced, we mean black-box-reduced.)

Rudich showed$^*$ in his PhD thesis that one-way permutations ($OWPs$) cannot be reduced to one-way functions ($OWFs$) --- i.e., given a $OWF$ $f$, one cannot construct a $OWP$ $\pi$ in the manner described above. In particular, what he showed is that Step 2 is not possible: i.e., there cannot exist a reduction algorithm $\mathcal{B}$ that breaks $f$ given an adversary $\mathcal{A}$ that breaks $\pi^f$.

Note that the above is a very strong statement: we are ruling out all reduction algorithms $\mathcal{B}$. One way to do this is through an "oracle separation".  What Rudich showed is that there exists an oracle $\mathcal{O}$ relative to which $OWFs$ exist, but any construction of OWP $\pi$ that uses $\mathcal{O}$ can be broken using an algorithm $\mathcal{A}^*$ that makes only a "few" (polynomially-many) queries to $\mathcal{O}$. The oracle $\mathcal{O}$ was chosen by Rudich as the random oracle, which is one-way with high probability -- in particular, it takes any algorithm "many" (nearly exponential) queries to a random oracle to invert it. The workings of $\mathcal{A}^*$ is a bit involved, but the high-level idea is it iteratively queries $\mathcal{O}$ on a "few" points in such a manner that it learns something new in every iteration. Since the implementation of $\pi$ is efficient, $\mathcal{A}^*$ can successfully invert $\pi$ using only a polynomial queries to $\mathcal{O}$. Note that $\mathcal{A}^*$ is only query-efficient, and runs in polynomial time only if it has access to a $\mathsf{PSPACE}$ oracle. But there is no way reduction $B$ could break the OWF ($\mathcal{O}$, i.e.) using $\mathcal{A}^*$ as the latter makes only a few queries to $\mathcal{O}$.

Matsuda and Matsuura strengthened the above result to show that a $OWP$ cannot be reduced even to injective $OWFs$ (arguably the closest primitive to $OWPs$). §1.2 in that paper contains a more detailed (although still intuitive) explanation of the Rudich separation .

P.S. Oracle separations have been used extensively in cryptography. Some other examples are:

Public-key cryptography cannot be based on OWFs: Impagliazzo and Rudich
Collision-resistant hash functions also cannot be based on OWFs: Simon

Other ways to rule out reductions are the so-called "meta-reduction" technique and the two-oracle technique.
Fischlin has a nice exposition on these techniques: that should be a good starting point for further reading. You can read more about black-box reductions in this paper by Trevisan, Reingold and Vadhan.

$^*$Rudich's result was modulo a conjecture, which was proved later by Kahn et al..


A hash function is a function taking an arbitrary length string as the input, and output a fixed length string. All hash functions are deterministic (correct me if I am wrong). Generally, a good hash function should map the inputs to its output range as uniformly as possible. Cryptographic hash functions have more requirements for security. The three most commonly used security properties are:

One-way: Given a hash value $h$ it should be difficult to find any message $m$ such that $h = hash(m)$.
weak collision resistance: Given an input $m_1$, it should be difficult to find a different input $m_2$ such that $hash(m_1) = hash(m_2)$.
collision resistance: It should be difficult to find two different messages $m_1$ and $m_2$ such that $hash(m_1) = hash(m_2)$.


Brute-force attacking One Time Pads feasible?

The interesting property for the one time pad is that every plausible plaintext (given the length constraint, i.e. of same length as the ciphertext, maybe including some padding) has a corresponding key which produces a certain ciphertext.

As mentioned in the comment by CodesInChaos, this key can be retrieved by simply XORing both plaintext and ciphertext (if you are using the XOR variant of the one time pad ... for the addition variant you'll have to subtract).

Also, assuming a random key, every plaintext has the same probability, given the ciphertext, as it has without knowing the ciphertext (apart from the length).

This is known as perfect secrecy – you can get no information from the ciphertext about the plaintext which you didn't know before (apart from the length, but this can be hidden to a certain degree by padding, too).

Every cryptosystem with the perfect secrecy property must have a key as least as long as the messages, and each key must be used only once. This is why a one-time pad or other perfect encryption systems are not used often in practice.


Does using crypto_stream_xor allow listeners to forge crypto_secretbox messages?

crypto_secretbox uses the first 32 bytes of XSalsa20 output as the key for Poly1305. Thus you are correct that using crypto_stream_xor on a known plaintext will reveal the authentication-key used by crypto_secretbox, allowing forgeries under that key and nonce.

Not using a key for multiple purposes is a general crypto design principle. Perhaps that's why the authors of NaCl didn't think of explicitly warning about this pitfall.


Schnorr signature security level as compared to AES/RSA

How does value of $p$ comes to $2^{512}$ for security complexity of
  $2^{72}$?

Personally, I couldn't connfirm this number, but rather landed at $2^{66}$. If you don't know how to find this number, just plug the $2^{512}$ into the complexity equation given and take the logarithm to the base two for better readability.

Note that Schnorr's complexity estimate for the field is based on the Index-Calculus Algorithm and doesn't yet take into account the Number Field Sieve (original paper as PDF) against discrete logarithms, which would give a different expression, namely $L_p[1/3,3^{2/3}]=e^{(3^{2/3}+o(1))(\ln p)^{1/3}(\ln\ln p)^{2/3}}$, that would yield a much lower required attack complexity.

  What is the equivalent AES and RSA key-lengths if we use $p$ of $1024$
  bits and $q$ of $512$ bits?

$q$ is the subgroup order and if you get a 512-bit subgroup you'll have roughly 256-bit security for this subgroup. $p$ is the field prime and with it being 1024-bit, you'll get roughly 80-bit security against NFS-based attacks. So the answer is: A 1024-bit RSA modulus will have a comparable security along with AES-128, where 48 key bits are constant zero'ed out. Note that just plugging-in $2^{1024}$ into the complexity equations is a dangerous business, as $o(1)$ hides an implementation-dependenant (constant) factor that was not accounted for. Rather you need a concrete data point as a basis for further extrapolation. Here's a more detailed treatment of keylengths: (simple) (complex) by Lenstra and Verheul.

  Since Schnorr is finite field signature scheme, what is the 'field
  size', 'group size' and 'subgroup size' in case of schnorr
  signature scheme?

$p$ is the field prime and its bitlength is the field size.
$q$ is the subgroup order and its bitlength is the subgroup size.
There's no relevant "group size" in this case (maybe one could say that's equivalent to the field size though)


This is a toy system that is used in didactic contexts as an introduction to RSA, in a way.

We have some prime $p$ (we are going to do the power operations modulo this prime).
If $m$ is the message (an integer in $\{1,\ldots,p-1\}$), we have some encryption exponent $e$, and encryption indeed works as $$E(m) = m^e \pmod{p}$$.

So for $p=23$, $e=9$ we indeed have $E(21)=17$, as $21^{9} = 17 \pmod{23}$.

The decryption exponent $d$ can be found by solving $ e \times d = 1 \pmod{p-1}$ (the $p-1$ is $\phi(p)$ and Euler's/Fermat's theorem tells us that $m^{\phi(p)} = m \pmod{p}$ for all non-zero $m$.) So exponentiation with $d$: $$D(m)=m^d \pmod{p}$$ is the inverse of $E$ and vice versa.

In your number example with $p=23, m=21, e=9$ we have $p-1=22$ and $9 \times 5 = 1\pmod{22}$ and indeed $D(17)=17^{5}=21\pmod{p}$ as expected: we get back our starting value $m$.

In #3 you know $E(m)=15$ so $m=D(15)=15^5 \pmod{23}= 7$. You should distinguish $E = E(m)$ from the exponent $e$.

So this system crucially depends on $e$ being kept secret, otherwise $d$ is pretty trivial to compute via Euclid's algorithm (that's how I found $d=5$ too) and anyone can decrypt. RSA depends on the fact that given $n$ of the form $pq$, with large unknown $p$ and $q$, makes it hard to find $\phi(n)$ and hence $d$ from $e$, as we find $d$ by solving $e \times d = 1 \pmod{\phi(n)}$ where $n$ is the modulus we are using, like $p$ in your case.


I think Substitution-Permutation Network is kept for historical reasons. Nowadays, we call SPNs even if Permutation is replaced by a general linear layer. Of course, the AES linear layer (concretely, MixColumns) is not a bit-permutation.


Factorization of RSA modulus using a qubic residue

Let $n = pq$.  By assumption, $3$ divides $\varphi(n) = (p-1)(q-1)$.  Without loss of generality, I assume that $3$ divides $(p-1)$ or, equivalently, that $p \equiv 1 \pmod {3}$.

Fact Let $p$ be a prime such that $p \equiv 1 \pmod 3$.  Let also $c$ be a cubic residue modulo $p$. If $y$ is a cubic root of $c$ then so are $y\cdot \omega \pmod p$ and $y \cdot \omega^2 \pmod p$, where $\omega$ is a non-trivial root of unity modulo $p$ (i.e., $\omega$ satisfies the equation $\omega^2 + \omega + 1 = 0 \pmod {p}$).

In your case, given $c \in \mathbb{Z}_n^*$, you know that $y$ and $z$ are two (distinct) cubic roots of $c$ modulo $n$.  Namely, $y^3 \equiv z^3 \equiv c \pmod n$.  In turn, this implies $y^3 - z^3 \equiv 0 \pmod n$ and thus $(y-z)(y^2+yz+z^2) \equiv 0 \pmod n$.  Since $n = pq$, it follows that

$(y-z)(y^2+yz+z^2) \equiv 0 \pmod p$, and
$(y-z)(y^2+yz+z^2) \equiv 0 \pmod q$.

Subcase 1 Assume $q \equiv 2 \pmod 3$ —in this case, cubic roots modulo $q$ are unique.  This implies that $y \equiv z \pmod q$.  But you cannot have then $y \equiv z \pmod p$ because otherwise you would have $y = z \pmod {n}$ (and $y$ and $z$ are supposed to be distinct).  Therefore, since $y \equiv z \pmod q$ yields $(y-z) \equiv 0 \pmod q$ and $y \not\equiv z \pmod p$ yields $(y-z) \not\equiv 0 \pmod p$, you get $\gcd(y-z,n) = q$.

Subcase 2 Assume now $q \equiv 1 \pmod 3$.  In this case, there is no guarantee that $\gcd(y-z, n)$ will reveal a factor of $n$.  Indeed, it may be the case that, even if $y \neq z \pmod n$, $y^2 + yz + z^2 \equiv 0 \pmod p$ and $y^2 + yz + z^2 \equiv 0 \pmod q$.  But you can always give it a try...


On the initializaton of the "xorwow" PRNG

OK, first things first. DO NOT UNDER ANY CIRCUMSTANCES USE XORWOW TO GENERATE ANY CRYPTOGRAPHIC SECRETS OR VALUES THAT SHOULD BE UNPREDICTABLE TO AN ADVERSARY.
Sorry to shout, but it is very important to point out that xorwow is not a cryptographically secure random number generator; it's an LFSR with a fake moustache.
I'm not sure why the wikipedia comment says that the first four need to be non-zero. In particular the states (0, X, 0, 0, 0), (0, 0, X, 0, 0), and (0, 0, 0, X, 0) would all transition to (0, 0, 0, 0, X) and would therefore presumably also be weak. It's important as with all LFSRs not to load up the register with all zeroes (so the first five variables should not all be zero). Also avoid setting the increment to an even value (the number 362437 in the wiki code). If you follow these two conditions the state will cycle through all $2^{192}-2^{32}$ values and different seeds just make you start at different points on the cycle and are pretty much equivalent. There's a small issue if the registers begin in a very spare state, they only slowly evolve out of being sparse, but over a large number of calls this will smooth out.
This would make the generator suitable for e.g. generating values for Monte-Carlo integration of a real valued function. BUT IT'S STILL NOT SUITABLE FOR ANY CRYPTOGRAPHIC PURPOSE. (sorry again for shouting).


El Gamal Signatures, Need help explanining a step, Where does the "775" come from? Image included

The question basically is how $300 - 61 \cdot 425 \bmod 880$ can turn into the value $775$, while a calculator returns a different value, likely $-105$.  The difference is that sometimes a remainder is taken to have a value in the range $(-N, N)$ rather than $[0, N)$.

$300 - 61 \cdot 425 = -25625$. So you can say that we're trying to find a value $x \cdot 880 + y =  -25625$. Now is can be $-29 \cdot 880 - 105 = -25625$ to find a value within $(-N, N)$, similar to finding $29 \cdot 880 + 105 = 25625$. $-105$ is then commonly called "the remainder"; it's what you would get if you would perform simple tail division yourself.

However, for cryptographic operations we generally try and perform operations in a group of order $N$ instead, with $N$ possible values in the range $[0, N)$.  so in that case we can take $-30 \cdot 880 + 775 = -25625$, and the result will be $775$, exactly $880$ more than $-105$ in other words. This is commonly called taking the modulus, although this value can also be called a remainder.

So to find the right value within your calculator you can simply add $N = 880$ if the result is negative. A little trick in programming languages is to perform ((X % N) + N) % N, so that an if statement can be avoided. Note though that the + N may cause an overflow for large values of $N$.


Repeatedly using same key on different plaintexts

It depends greatly on what form and mode of encryption you use.

For any stream cipher or a block cipher used in a psuedo-stream mode such as CTR or GCM then reusing a key/IV pair even once is absolutely fatal. Never, ever use a static key with them, and if you do, never, ever reuse an IV. They are strictly for one time use keys negotiated via a key exchange algorithm for a particular session.

For modes such as CBC key reuse isn't a big issue even if you accidentally use the same IV again. Re-using the same key/IV will let an attacker determine whether two messages have a common prefix, but won't inherently leak information leading to a breach of the key or plaintext.

So, if you are using temporary keys AND trust your random number generator to be secure and strong then the advantages of CTR or stream mode are compelling especially if speed/parallelization is a concern. If either of these are not the case, such as a pre-shared key or there is no good entropy source, or you don't benefit from the stream cipher characteristics then something like CBC is the way to go.


Is RC4 cipher just xoring plaintext with a random sequence seeded by key?

Is there something else in the algorithm?

No, that's it: just a pseudorandom generator (which in RC4's case turned out not to be that random) whose output is XORed with the message.

  Is there a general name for stream ciphers that use a XOR with a (pseudo-random) sequence seeded by key?

Yes — it's stream cipher.

(While you could certainly apply a stream cipher using different invertible binary operations (e.g., addition or subtraction modulo 256), that provides absolutely no benefit over XOR, so nobody ever does it. In both theory and practice, everybody will think of XOR when you say "stream cipher".)


Differences between hash- and encryption algorithms?

When do we use a hash algorithm and when do we use an encryption algorithm (a cipher)?

Hash functions are typically used to map an arbitrary-length (usually long) input into a fixed-length (usually short) and random-looking value. E.g., SHA-256 always outputs a 256-bit random-looking string (or digest) for any given input.

A very common property of hash functions is collision-resistance, i.e., it is very hard to find two inputs that generate the same output. This is very useful when the input size is very long, which implies that we can compress a big file/string into a small one while still maintaining its "uniqueness". (Of course, theoretically, there are many many long inputs that generate the same short output due to Pigeonhole principle, but they are very hard to find given reasonable computing resources.) Based on this property, hash functions have many good applications. For instance, one can use the hash values of big files to efficiently find duplicates, and some websites often publish the hash values of their downloadable application installation packages to guarantee integrity. However, hash functions themselves are not directly related to data privacy or confidentiality.

The other property that hash functions (are expected to) have is that they output random-looking values. This can be used to generate random keys given non-random (but high-entropy) inputs, i.e., the so-called key derivation functions.

Encryption algorithms (more precisely, encryption schemes) are designed to "hide" the input/plaintext with the output/ciphertext such that no one except those having secret keys can decrypt the ciphertext to get the original plaintext. They at least provide data confidentiality, and authenticated encryption schemes also provide integrity (hash functions can be used here).

  How difficult it is to reverse hash- and encryption algorithms?

Hash functions by design are hard to reverse, so are encryption algorithms without knowing the secret key. But if you know the key or if you want to play with the encryption algorithm with any key, then you can easily reverse it with a decryption algorithm using the same key. So, here the simple difference is that hash functions do not have keys. (Note that keyed hash functions are often discussed in the topic of message authentication codes.)

  From the theoretical/mathematical perspective, what differentiates a hash- and encryption algorithm?

Hash functions normally map long inputs into short ones while encryption algorithms often do the opposite to introduce randomness (to hide the input messages). Hash functions are deterministic while encryption algorithms are often probabilistic (otherwise the encryption scheme cannot be IND-CPA secure). Well, regarding similarities, they both generate random-looking outputs.


Standard parameters for Boneh–Lynn–Shacham signature?

Well, the Boneh-Lynn-Shacham "BLS" signature scheme is currently in the process of being standardized through an Internet Draft named "draft-irtf-cfrg-bls-signature-00" (a working document of the Internet Engineering Task Force "IETF"), which you can track here. It appears Algorand might be behind this process, along with Dan Boneh's own support.

As stated in there:

  There are two variants of the scheme:

  (minimizing signature size) Put signatures in G1 and public keys
     in G2, where G1/E1 has the more compact representation.  For
     instance, when instantiated with the pairing-friendly curve
     BLS12-381, this yields signature size of 48 bytes, whereas the
     ECDSA signature over curve25519 has a signature size of 64 byes.
  (minimizing public key size) Put public keys in G1 and signatures
     in G2.  This latter case comes up when we do signature
     aggregation, where most of the communication costs come from
     public keys.  This is particularly relevant in applications such
     as blockchains and compressing certificate chains, where the goal
     is to minimize the total size of multiple public keys and
     aggregated signatures.

While they do not (yet) specify explicit parameters that are to be used, they do refer to the Internet Draft "Pairing Friendly Curves", which in turn has multiple recommendations depending on the level of security you want to reach.
Regarding the above quote, it notably lists BLS12-381 in the recommendation to have 128 bits of security.

Also, when compared with ECDSA, they mention that (emphasize mine):

  The following comparison assumes BLS signatures with curve BLS12-381,
  targeting 128 bits security.
  [...]
     In terms of sizes, ECDSA uses 32 bytes for public keys and 64 bytes
  for signatures; while BLS uses 96 bytes for public keys, and 48 bytes
  for signatures.  Alternatively, BLS can also be instantiated with 48
  bytes of public keys and 96 bytes of signatures.  BLS also allows for
  signature compression.  In other words, a single signature is
  sufficient to anthenticate multiple messages and public keys.

So it appears that the current "standard" is to have ~384 bits of signature to reach 128 bits of security, which means having $3b$ bits signatures for $b$ bits of security. (BN curves having "lost" favors, as Bristol said already and their current 128 bits contender being BN462.)

Also, notice this is a working document, and as such is not complete. For instance it is missing things that are yet to be added:

  TBA: additional discussion on this, e.g.  [Ristenpart-Yilek 06], and alternative mechanisms for securing aggregation against rogue key attacks, e.g.  [Boneh-Drijvers-Neven 18]; there, pre-processing public keys would speed up verification.

And the rogue key attack is typically something important to defend against in the case where we want to have aggregate signatures, which is one of the nice features of BLS.

Notice that in pairing based crypto we had to move significantly our security estimates within the last 3 years most notably because of the advances in the FFDLP (see [KB16]), with your latest reference [BD 2019], being the current state of the art regarding security estimates and recommendations.

So it might still take a while until the above-mentioned IETF draft is finished and becomes an actual "standard", but this is in process.


The counter mode encryption (and similarly the decryption) with AES work as
$$C_i = AES(key,nonce,i) \oplus m[i]$$ where the nonce and index $i$ is used to encrypt the $i$th block with the x-or of the output of the encryption.
The cryptographic algorithms work on bytes and you can consider it as a byte array. Now you need to fill the byte array with your random 8-byte values on the lower index and the rest is set to 0.
If you want to have the random access that CTR enables, you can set the upper bytes to the index $i$ within 64-bit representation.
If you are encrypting sequentially, then after setting the counterpart to zero, you need to implement a byte array incrementer. If we represent in hex then we need two hex char per byte;
1b4fe8364as4a8100000000000000000    //initial
1b4fe8364as4a8100000000000000001    //counter incremented
1b4fe8364as4a8100000000000000002    //counter incremented
1b4fe8364as4a8100000000000000003    //counter incremented
..
1b4fe8364as4a81000000000000000FF    //counter incremented
...

So I guess you can randomly generate nonce

There is a common problem here, 64-bit nonce is vulnerable to collisions. After $2^{32}$ random nonce generation under the same key one will have collisions with 50%. The 50% is not negligible, one must stop way before that. A better way is either

Generate the nonce sequentially, which may some other problems as system failures can cause re-use of the old values were the easiest mitigation is using a fresh key. Or,
Use larger random like AES-GCM uses; 96-bit nonce. This is safer to use randomly. Keep in mind that, this will limit the number of block encryption to $2^{32}$ and this makes $2^{36}$ bytes and that is $\approx 68.71$ GB.

And remember, AES has a 128-bit block size regardless of its key sizes 128, 192, and 256.
Normally, the cryptographic libraries handle those parts for you. You don't need to worry about those like Java's IvParameterSpec.


Can I use the secret part of a asymmetric encryption keypair as a symmetric encryption key?

The HMAC calculation is used as a KDF here. So 3 keys are derived.

Let's start with the statement "In practice, if you know one, you'll know the other.". This is incorrect. The KDF construction uses a one way function so that you cannot get to the input keying material (or seed) s. This means that if an adversary gets hold of the symmetric key c that you cannot calculate either s and therefore e or d.

There is another more theoretical problem in the sense that using d both for HMAC as for "symmetric secret key" then you're using the same value for multiple algorithms, breaking their security claim. It might be that there is some mathematical algorithm that makes the value of s vulnerable. From a practical perspective that's highly unlikely as a HMAC with a known string will not be a structure that can be abused for this kind of attack - but I think it is worth mentioning anyway. For instance, an auditor may ask nasty questions about it.

From a more practical point there may be an issue when it comes to side channel attacks. If these can be combined then there may be a practical issue when the keys are not separated (this is of course a blatant copy of the comment by fgrieu below).

And that's about it; the reason to separate the keys is key separation itself. If you want to break that rule then that's your decision, but it is certainly not considered good cryptographic practice. I'd only do such tricks if there is no other way.


How to prove element equality in G1 using Groth-Sahai proofs

First of all, the idea of proving element equality does not make much sense, since that would reveal the secret element. $prove(X == T)$ with secret $X \in G_1$ and public constant $T \in G_1$ reveals the value of $X$. What I was looking for instead is $prove(g_1^x == T)$ with public constants $g_1, T \in G_1$ and secret scalar $x$.

It tuned out that type 2. multi-scalar equation in $G_1$ was what I was looking for. Since both left hand side and right hand side of those equations are elements in $G_1$, this is exactly what I needed. The special case to use was the liniear equation:

$A^y = T_1$

with public constants $A, T_1 \in G_1$ and private scalar $y$.

Note: Here I used the multiplicative notation for the operation in $G_1$ as it is done in the BeleniosRF paper; the GS paper uses the additive notation.


What is the origin of the word "Keccak"?

According to J.-P. Aumasson (who's one of the authors of another SHA-3 finalist, BLAKE, and who participated in the cryptanalysis of Keccak), the name "Keccak" is a variant spelling of "Kecak", a type of Balinese dance.

So far, that's the most authoritative reference I've been able to come up with.  It should be noted that naming crypto primitives after dances is hardly a new thing; see e.g. D. J. Bernstein's "latin dances" (Salsa, Rumba and ChaCha).


Should we sign-then-encrypt, or encrypt-then-sign?

Assuming you are asking about public-key signatures + public-key encryption:

Short answer: I recommend sign-then-encrypt, but prepend the recipient's name to the message first.

Long answer: When Alice wants to send an authenticated message to Bob, she should sign and encrypt the message. In particular, she prepends Bob's name to the message, signs this using her private key, appends her signature to the message, encrypts the whole thing under Bob's public key, and sends the resulting ciphertext to Bob. Bob can decrypt, verify the signature, and confirm that this indeed came from Alice (or someone she shared her private key with).  Make sure you use an IND-CCA2-secure public-key encryption scheme and a UF-CMA-secure public-key signature scheme (i.e., one that is secure against existential forgery attack).

Justification: The reason to do this is to defeat some subtle attacks.  These attacks are not necessarily a problem in all scenarios, but it's best to harden the approach as much as possible.  A complete explanation would take more space than is available here, but see below for a sketch of the reasoning.

For a detailed analysis about whether to sign first or encrypt first, the following is a good resource: Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML.

I don't recommend encrypt-then-sign. It could work, but it has some subtle pitfalls in some contexts, because the signature does not prove that the sender was aware of the context of the plaintext. For instance, suppose Alice's SSH client sends the message "Dear SSH server, please append my public key to /root/.ssh/authorized_keys -- and you can know that I am authorized because I know the root password is lk23jas0" (encrypted then signed with Alice's public key), and the SSH server acts on it if the root password is correct. Then Eve can eavesdrop, capture this message, strip off Alice's signature, sign the ciphertext with Eve's own key, and send it to the SSH server, obtaining root-level access even though Eve didn't know the root password.


Could RDRAND (Intel) compromise entropy?

First of all, there is a difference between writing to /dev/random and/or /dev/urandom and increasing the entropy count maintained in the Kernel.

This is the reasony why, by default, /dev/random is world-writable - any input will only augment, but never replace the internal state of the RNG; if you write completely predictable data, you're doing no good, but no harm either.

If, on the other hand, you write to /dev/random using a special ioctl (and that does require superuser privileges), you can actually increase the entropy estimate.

If you are able to do that (and if you are, you could as easily replace /dev/random with /dev/notsorandom and be done with it), /dev/random degenerates to the behavior of /dev/urandom: Usually, reads from random are supposed to block until at least as many bits of entropy have been written to the internal pool than are requrested, while urandom returns as much "randomness" as requested.)

If you manage to write predictable bits to the pool, but tell the kernel to credit them as unpredictable data, the next reader(s) of /dev/random will receive random numbers that only deterministically depend on the current internal state of the entropy pools, and not on "truly random" events like disk seek times and keyboard inputs.

However, unless you are able to perform that attack from the very installation of the operating system, you don't actually know that internal state! Predicting it from /dev/random outputs is at least as hard as reversing SHA-1 (and that's perceived to be very difficult). This is also why it can be reasoned that, for the exception of directly after a fresh OS install, urandom can be considered to be "random enough" for all purposes, cryptographic or not.

Now let's have a look at the actual implementation of RdRand in drivers/char/random.c:

The only place the possibly malicious RdRand instruction is ever used is in the output functions of the random devices. It is XORed with the "actual" output of the "classical" Linux RNG right before that output is returned to the caller.

Since information theory tells us that when we XOR a chosen string with an unknown string, we can't predict anything about how the resulting string will look after the transformation, there is nothing to be gained from subverting the RdRand instruction, at least the way it is currently used in Linux.

Update:
Some suggest that a very clever CPU might interpret calls to RdRand as a trigger for a backdor that, for example, replaces the subsequent XOR with a MOV.

I'd say that's theoretically possible, but exponentially harder to implement than to just skew the output of RdRand directly, e.g. by returning the keystream of AES-CTR under a key known only to the adversary as "random numbers".

There would have to be checks for the specific code sequence used in the Kernel; if that ever changes (e.g. by surrounding the RdRand call with some dummy XOR operations), a microcode update to adapt the heuristic would have to be widely deployed or people would get suspicious very soon.

Treating the RdRand instruction (or an equivalent on a different architecture) as just another entropy input (without increasing the estimated entropy, to be safe), would probably make the RNG even harder to subvert.

Second update:
The issue has been discussed on the kernel mailing list twice: Once in 2011, started by a patch submitted by an Intel engineer and followed by a lot of discussion about security, and once again in 2012, which eventually lead to a patch implementing the current approach. Even the concerns about triggering a backdoor that changes the behavior of some instructions (e.g. XOR or MOV) has been mentioned. As far as the XOR construction is concerned: The Linux folks claim that the XOR approach is supposedly more secure than hashing the RdRand output into the entropy pool, though some of us here are not really persuaded about that.


How to prove that I am part of a list without revealing my identity?

The scheme that solves your problem is called Zero Knowledge Proof of Set Membership
ZKP for Set Memberships use Accumulators. Crypto++ library provides an implementation of the accumulator


Which blind signature schemes exist, and how do they compare?

I'm still a newbie in the field, but trying to learn something about it I ran into these two papers that you surely know, in case not I'll point them out:

Blind signatures for untraceable payments, Chaum
Provably secure blind signatures schemes, Pointcheval

By the way if you look at the introduction of the second title it seems what your looking for.

A specific link on Electronic Cash from RSA Laboratories:

What is Electronic Money

By studying blind signatures I've read about a scheme based on ElGamal Signature Scheme, I'll provide the information I was able to glimpse.

You can find more details at the following links:

IEEE, A blind signature scheme based on ElGamal signature
Citeseerx, Generalized blind signature schemes

Blinded ElGamal:

Performances:

  Owner Alice needs to compute two online exponentiations modulo $p$
  with a |$q$| bit exponent and one offline inverse modulo $q$.

  Notary Nancy needs to compute just one online exponentiations modulo
  $p$ with a |$q$| bit exponent.

  Verifier Victor needs to compute two exponentiations instead of the
  three ones required for standard ElGamal scheme.

Note: you can find further references for even more efficient variants in the links I provided.

Patents:

I have no clue!Sorry about that...

Simplicity:

I got it all clear, if reading the papers you have any doubts post them and we can check together!


Can I use asymmetric encryption for more powerful write-protection?

What you describe is a digital signature, which works using methods very similar to the one you suggest. Examples include elgamal-signature and RSA signature schemes (the second of which I would recommend you read).

Digital signatures allow you to provide a public signature that 'proves' you provided the message. As the author, you would produce database $m$ and a signature $s=s(m)$ confirming it is what you wanted.  You then provide your program with an algorithm $V$, called a verifier.  The verifier tests whether $s$ is a valid signature for $m$. If the signing algorithm was deterministic, an example verifier could just recompute the signature.

As with all crypto code, be wary of implementing a signing algorithm yourself, since there are lots of subtle pitfalls you may hit, such as the RSA homomorphic property.


ECB sucks big time. CBC sucks slightly less, but still a lot.

Generally speaking, when you begin to use an encryption system, it is to achieve a number of security-related properties, e.g. confidentiality and integrity of data. An "encryption mode" is a way to turn some elementary cryptographic function (e.g. AES) into something that can process messages of variable but potentially large size, in a way which achieves these properties. AES itself is called a "block cipher", which means that it really is a key-indexed family of permutations in a space of blocks of bits of a given size. In other words, AES does not encrypt message, no more than a brick provides housing. The encryption mode makes a system that encrypts messages in the same way as a mason assembles bricks to make a house.

Classical modes of operation extend a block cipher into a system that can encrypt a message and hopefully provide confidentiality. ECB does a bad job of it (see the penguin pictures in that Wikipedia page). CBC is better but still flawed (e.g. if the IV is predictable, chosen plaintext attacks can be used to leak information; also, it requires padding, whose processing can lead to padding oracles). Historically, CBC was much used because it seemed to be the best we had, but that was only when compared to ECB, which is atrocious in that respect.

Most importantly, classical modes provide encryption but not integrity. In almost every conceivable scenario that warrants use of encryption, integrity is also needed. There are algorithms called Message Authentication Codes that can provide integrity (but not encryption). Some MAC can even be built out of block ciphers, with yet again some "modes". It turned out that getting encryption and integrity at the same time is not easy to get right. A lot of protocols got it wrong (e.g. SSL/TLS, ant it created a lot of trouble). Thus cryptographers took up to the challenge, and decided to make new modes of operations that provide encryption and integrity, and do it properly. The general term for that is authenticated encryption (specifically, "AEAD" for authenticated encryption with additional data). The most well-known of these modes will be GCM, CCM and EAX. These modes are built over a block cipher that processes blocks of 16 bytes (128 bits), usually AES.

It is also possible to make AEAD systems out of other things than block ciphers. E.g. one can assemble (again, with great care) the stream cipher ChaCha20 with the MAC algorithm Poly1305, to get a very decent AEAD system (see RFC 7539).

A very frustrating feature of cryptography is that you cannot test for security. You can read documents and watch videos and make some code that runs, and add lots of unit tests that show you that your creation works and data flows in and out properly. None of these tests will tell you whether the result is secure. The best way to test security (and it's not a good way, it's just that all others are worse) is the combination of the following:

You absorb all the known published science on the subject. For instance, for encryption, everything I wrote above should be known to you, and much more.
You write your stuff while being extra careful, and documented precisely why all the attacks you know of (and there should be many, thanks to point #1) cannot work.
You show your work to the world at large, and challenge all cryptographers to come test their skills against the might of your intellectual creation.
While the said cryptographers close for the kill and feast on the corpse of your erstwhile proud system, and explain in graphic details all the amusing ways they found to metaphorically disembowel your security, you slump in a corner and sob pitifully.
Then you get up, and start again at step #1, to do it properly this time.
After a few iterations, if you work hard, you may finally achieve the creation of a system that actually survives the onslaught of your vindictive colleagues. Congratulations! The security of your encryption system is not proven yet (in fact, theoretically speaking, it is not clear that a secure encryption system can really exist at all), but at least you will have some reasonably good reasons to assert that if there still are weaknesses in your last creation, they are not obvious.


What is the best way of deterministically choosing N of M, given 32 bytes of sha256?

Is there an efficient way to do this?

32 bytes of "good randomness" provided by hashing some secret value gives much less entropy than required to directly compute a sample of 100 items from a list of 100000. If this is required for any cryptographic purpose, you must use a good CSPRNG to convert your starting entropy into as much randomness as you need.
If by efficient you mean "a one-liner", then probably not

Or should I use something like (sha256hmac(n, H) & 0xFFFFFFFFFFFFFFFF) % N and skip duplicates. (Where n is 0..N-1.)

DO NOT attempt to roll your own CSPRNG to generate what you need
What you are describing (repeated application of an HMAC to a changing value) is approximately an HMAC_DRBG described by NIST. If you want to use something along those lines to generate your bitstream, use that instead as it is far more secure than what you have described.
Furthermore, once you have a strong source of random bytes (e.g. the NIST DRBG), it is NOT enough to simply generate some bits, say $k$ such that $2^k$ is greater than $N = 100000$, take this mod $N$ and be done with it. When doing this, as $N$ will never perfectly divide $2^k$, you are inroducing bias into the random numbers generated; the smaller $2^k$ is in comparison to $N$, the greater the bias. Where $k$ is 64, as in the example you proposed, the bias is approximately $2^{-48}$. This may not seem like a lot, but if we consider the negligible function as $2^{-b}$, where $b$ is the "bits of security" of some cryptographic function, as we often do, then your RNG has only 48 "bits of security". Conseridering we are aiming for closer to 256, I would go as far as to suggest using a full 32 byte word of data from the CSPRNG to generate each of your indices.
This is quite a computationally intensive process, however, and it may be a better idea to, instead of taking a modulus in this manner, just generate the minimal number of bytes required to get a single index between 0 and $N$ and discard those bytes if they are at or above the highest multiple of $N$ smaller than the possible number represented by your bytes. For example, in 3 bytes with a max. possible value of 16777216: if the value is below 16700000, then take that mod $N$ and use the result, otherwise discard it and generate 3 fresh bytes from the CSPRNG stream. This could take theoretically infinite time to complete, but less on average than the previous method.


SHA-1 – Would using a SHA1 signature be a risk?

Yes, it is.

A chain is as strong as its weakest link. Strengthening one link, e.g. using a SHA-2 certificate instead of a SHA-1 certificate, will not strengthen any other link.

You cannot prevent someone tricking you into signing a SHA-1 collision, just by using a SHA-2 certificate. A SHA-2 certificate is a certificate that was signed using SHA-2 by the certificate authority that issued the certificate. Having such a certificate will not give you magic super powers. You will still have to use your own private/public key pair wisely.

Regarding the follow-up questions, you would of course have to generate the collision prior to signing it the first time. The second signature might be added in at least three different ways:

In parallel with the first signature, over the same data and consequently using the same hash. In this case you will obviously get a collision the second time as well.
Over the signed data including the first signature. It might be harder to generate an original collision that will still be collision for the second signer in this scenario. On the other hand, this doesn't matter unless the second signer gets the to-be-signed data with physical security directly from the first signer.
Counter signature of the first signature blob. Since the first signature blob is already compromised by a collision, the counter signature will by extension also be compromised.


There are two formulations which are equivalent. One formulation is where the simulator outputs the verifiers view and the other where the simulator outputs the verifier's output. In neither case does the verifier's output need to be present. However, since it depends the verifier, and we quantify over all PPT verifiers, the simulation must work also where the verifier outputs accept/reject on top of whatever else it may want to output.

These formulations are equivalent since the distinguisher can just run the verifier on its view to get the output.

Just to complicate things, note that if a definition is used that allows an expected polynomial-time verifier and simulator, then the distinguisher cannot run the verifier on its view unless it too runs in expected polynomial-time (and things are typically not formalized this way). However, this really isn't very important and you should be able to ignore this complication.


Challenge-based symmetric-key authentication works a bit like this:

Server picks a randomly chosen challenge and sends it to the client.
Client "transforms" the challange with his key and send the result back to the server.
Server does the same transformation with the same key, and verify if the two matches.

The transformation can be an encryption algorithm, but usually well-designed system would use a MAC (message authentication code) such as HMAC.

In your case, the nonce is most likely a challenge, although 3 character only provides 24-bit (<21 bits if ASCII-only) insecurity.


Is There an Opensource Manual Calculation of AES-128 bit?

Project Nayuki has an Excel sheet in binary, XML and OpenDocument format. The code doesn't include any  Vusial Basic or Macros, they used only the spreadsheet's math functions; VLOOKUP, BITXOR, DEC2HEX, and HEX2DEC.

They have also, a nice video for AES on Youtube and a flash animation if you can run somewhere.


As you must know, ADFGVX is a German cipher from World War I. It was broken by the French (Painvin) during that war, but not without a major effort, and only on certain days.

It uses fractionation and a Polybius square, followed by a columnar transposition based on a keyword.

In Milton F. Friedman's Military Cryptanalysis, Part IV, pp. 103-149, he goes into detail about how to break this cipher.

There is also a useful paper from 1984, Konheim, A. G. (n.d.). Cryptanalysis of Adfgvx Encipherment Systems. Lecture Notes in Computer Science, 339–341. doi:10.1007/3-540-39568-7_26 (an extended abstract)

Konheim presents a four-step cryptanalytic technique to break ADFGVX.

Determine which column vectors are adjacent in the array.
Determine the relative order of the pairs of column vectors.
Recover the substitution.
Recover the transposition order of the columns in the array.

One thing that could be looked at first is this: perhaps the Polybius square is not a mixed alphabet after all, but alphabetical.


Does key renewal increase complexity of MAC forgery?

This depends on the MAC because there are different kinds of attacks to consider.

If the best attack is randomly trying authentication tags, then the key does not matter.
If the best attack is brute forcing the key, then key renewal does mean that the attacker has to "start anew", but as long as the key space is large enough that the probability of finding the key is small, that probability does not decrease all that much.
If the MAC is broken and admits other attacks, then key renewal may make attacks more difficult (e.g. if a large number of known MACs are needed) or easier (e.g. if some keys are weak).

MACs such as SipHash or many AES-256-based MACs fall under the first case. It is much faster to randomly guess a correct MAC value than guess a correct key, because the key space is larger than the tag space.

On the other hand, HMAC is sometimes used with a key that is shorter than the output (e.g. 128-bit key and HMAC-SHA-256). If the MAC tag is not truncated, then the fastest known attack is brute forcing the key. This is the second case.

Regarding the third case, one example is MAC misuse, such as CBC-MAC with variable length messages, which becomes secure if you renew the key on every message. A short AES-GCM tag is also secure as long as you do not reuse the key too many times.


What are the major differences between theoretical cryptography and applied (practical) cryptography?

I cannot tell any obvious feature to differentiate them, but I think you can distinguish theoretical cryptography and applied cryptography from the writing style of papers. In the paper about theoretical cryptography, they usually prove some cryptographic primitive(s) imply another one or construct some schemes or protocols that could be reduced to a standard assumption (e.g., identity-based encryption can be reduced to BDH assumption). Nevertheless, in the paper of applied cryptography, there are usually some implementation results which includes, for example, how to set exact security parameters or message length and so on. Furthermore, theoretical cryptography papers are usually published in conferences like CRYPTO, EUROCRYPT, and TCC, and applied cryptography papers are usually published in conferences like USENIX and ACM CCS.


How simple can the PRP used in the Even-Mansour scheme be?

The permutation used for Even-Mansour needs to approximate a random permutation. This is the model in which all of the $r$-round Even-Mansour proofs are done. If you have a permutation that is distinguishable from random in a small number of queries, those proofs become null and void—though in some cases the cipher may still be secure.

Now, it is perfectly reasonable to wonder about the exact limits of this approach like you did, and in fact people have: this is a popular cipher design approach otherwise known as "key-alternating cipher". The AES itself is probably the most famous instance of it. You can model the AES as
$$
P'(\dotsc P(P(m \oplus k_0) \oplus k_1) \oplus k_2) \dotsc) \oplus k_{10},
$$
where $$P(x) =\mathsf{MixColumns}(\mathsf{ShiftRows}(\mathsf{SubBytes}(x)))$$ and $$P'(x) = \mathsf{ShiftRows}(\mathsf{SubBytes}(x)),$$ and $k_i$ are the keys produced by the key schedule.

While the AES is not provably secure, since each of those permutations is way too simple to behave as a random permutation, heuristically this works out against known attacks given enough rounds. But in this case, the Even-Mansour results are of little use (besides confirming that the high-level design approach is sound), and concrete analysis against differential, linear, etc cryptanalysis is much more valuable.


How to construct a next bit predictor from a distinguisher

Your idea for constructing a distinguisher from a predictor is fine, assuming you know that the predictor predicts the last bit.  The more general statement is: if you can predict any bit of the output, say the $i$th bit, given the first $i-1$ bits, then you can also build a distinguisher.  A similar idea to what you showed also works to prove this statement.

For constructing a predictor, your idea doesn't work; we have to work a bit more.  The problem is you don't know which bit is predictable; it could be any of the bits.  Here's how we handle that.  We prove that if none of the bits is predictable, then there can be no distinguisher.  You prove this using a hybrid argument (do you know what that is?).  Then, take the contrapositive, and you get the result you wanted.


Why is the payload size is restricted when using RSA

When you're talking about RSA-1024, the "1024" refers to the bit length of n, so n is 128 bytes long. Now let's take a look at RSA decryption process :

In order to recover your plaintext, you will compute
\begin{align*}
c^d \mod n &= m^{e*d}\mod n\\
& = m \mod n
\end{align*}
You can see that if $ m > n$, i.e. if $m$ is more than 128 bytes (in case of RSA 1024), the result will not be $m$, hence the size limitation.


Could a strong round function be immune to slide attacks

Wikipedia is correct: any cipher that consists of a repeated number $n$ of iterations of the same function $F$ is vulnerable to the slide attack. Once you find a slid pair, the security of the cipher degrades to the security of $F$.

Generally speaking, 1 application of $F$ is not enough to withstand standard attack methods (e.g., differential, linear, etc). When you have a slid pair $(x, F^n(x)), (F(x), F^{n+1}(x))$ you can, for example, attack $x$ and $F(x)$ directly, thus recovering the key. What you can do precisely with a slide attack is specific to the cipher in question, however.

Note that if $F$ itself is ideal, then the slide attack is not effective. But in that case iterating $F$ is pointless, since you can use $F$ directly at $n$ times the speed!

There are two simple ways to prevent slide attacks:

Make your block size large enough. If your cipher has a 256-bit block, it will take (in the optimal case) $2^{128}$ plaintext-ciphertext pairs to get a slid pair, in which case it doesn't really matter whether slide attacks apply or not.
Make each round different. This doesn't need to be a large modification; for example, the Keccak permutation simply xors a different constant (the $\iota$ function) into the state at the end of each round, and this suffices to eliminate slide attacks.


Which crytographic libraries to use for Elliptic Curve Cryptography and Bilinear Pairing?

you can use pbc library (The Pairing-Based Cryptography Library).
https://crypto.stanford.edu/pbc/


What should an identifer in the client-server model?

There are a few non-standard/confusing things about this picture. I'll address them in a minute.

1) Yes, you can set a fixed alias for each party. You will want to make sure that the aliases are unique, public, and verifiable.

2) You're right that RSA is better to use here than AES. In particular, the encryption scheme here is asymmetric, that is, the encryption key is different than the decryption key. Since AES is a symmetric key primitive, it wouldn't really make sense to use it here.

The notation $E(PR_a,K_s)$ is syntactically incorrect. You don't encrypt using the private key in an asymmetric encryption scheme.

However, the real problem seems to be that you want to be using a signature scheme in that particular location rather than an encryption scheme. To understand why this is the case you need to understand the difference between privacy and authenticity:

Privacy ensures that nobody can read a message except for the person/people holding the decryption key. Authenticity ensures that a message really was sent by a particular person. Encryption schemes generally provide only privacy. However, if you want authenticity in the asymmetric setting, you probably want to use a digital signature scheme -- that is, person A can sign a message, and anybody can verify that the message was in fact signed by A.

(For RSA in particular, you could think of the decryption function as a signing function and then think of the encryption function as a verification function and this will give you a digital signature scheme. But this is not at all true in general. It only works for RSA because of the particular details of the RSA algorithm.)


What happens if we choose the random secret keys in Diffie-Hellman greater than prime?

The modulus operation $\pmod p$ is performed at each step and reduces the result into $\bmod p$. And a clever implementation can use the Fermat's Little Theorem instead of taking the power than reducing to modulo $p$. After that it's possible to use the modular version of repeated squares algorithm or similar.

Example 1) code used from  sublimerobots

sharedPrime = 23    # p
sharedBase = 5      # g

aliceSecret = 600     # a
bobSecret = 1500      # b

Alice Sends Over Public Chanel:  8
Bob Sends Over Public Chanel:  4

Privately Calculated Shared Secret:
Alice Shared Secret:  2
Bob Shared Secret:  2

Example 2)

sharedPrime = 23    # p
sharedBase = 5      # g

aliceSecret = 6000000     # a
bobSecret = 15000000   # b

Alice Sends Over Public Chanel:  8
Bob Sends Over Public Chanel:  4

Privately Calculated Shared Secret:
Alice Shared Secret:  2
Bob Shared Secret:  2

I think you are confusing the mathematical representation and the actual value.

In the sense of optimization, the code from sublimerobots is not good. Actually. instead of

bobSharedSecret = (A**bobSecret) % sharedPrime

a faster version

bobSharedSecret = pow(A,bobSecret,sharedPrime)

which uses modular binary exponentiation.


Will ANY prior knowledge assist in determining contents of a SHA1 hash?

It all depends on whether the rest of the input is guessable.

The best attack we know for finding the input to SHA1, given the output and partial knowledge about the input, is a brute-force attack:

For each candidate at the full input, try hashing that input with SHA1 and see if it matches the known output.

So, the running time of the attack will be proportional to the number of candidates we need to try.  If part of the input is known, the running time will depend on how easy it is to guess/predict the rest of the input.

For instance, if the unknown part of the input is a 4-digit PIN, and the rest of the input is all known, then the system is definitely vulnerable.  There are only $10^4 = 10000$ candidates for the full input, so you can try each one of them.  This won't take very long.

As another example, if the unknown part of the input is a 128-bit secret value, and you have no way of predicting that input, and all 128-bit values are equally likely, then the system is safe.  There are $2^{128}$ candidates for the input, and you can't try them all.  Also, they're all equally likely, so you can't even get a speed-up by trying the most likely candidates first -- all the candidates are equally likely.

In general, if the entropy of the secret part is at least 128 bits, you should be good.


Which algorithm can be performed by humans?

Every classical cipher can be used without a computer's assistance; while simple mechanical ciphers can fall into the "classical cipher" category, in general classical ciphers are pen-and-paper ciphers, almost all of which are more secure than your "press the key to the right of the real one." Vigenere, for instance, has flaws; however, it is much more secure than "press the key to the right of the real one," because the latter is a special case of a monoalphabetic substitution cipher (the whole class was broken in the 9th century CE), while the former is a polyalphabetic substitution cipher which was broken in the 19th century.

More recently, you have some newer schemes that can be done without the aid of a computer. Neal Stephenson's book Cryptonomicon featured as a plot point the Solitaire scheme, which requires only a deck of playing cards to implement. Solitaire has some weaknesses, but is likely better than Vigenere or other previous ciphers. More secure than Solitaire is RC4; this could be implemented by hand, but would be complicated (to ease matters, you could probably have a reduced-security version that could also use a deck of cards for the state).

Anything that's truly highly secure will probably be not realistic to implement by hand (except an OTP, but that's really hard to pull off the preconditions), because they are designed to be easy for a computer to do, and computers are good at different things than people. But there are certainly options better than monoalphabetic substitution.