Can an attacker recover the key if a Poly1305 collision is known?

Yes, the attacker can recover the key with high probability in the event of such a collision.  For example, in two-block messages $m_1 \mathbin\| m_2$ and $m'_1 \mathbin\| m'_2$, this means that $$m_1 r^2 + m_2 r = m'_1 r^2 + m'_2 r,$$ so the key $r$ is a root of the quadratic polynomial $$(m_1 - m'_1) r^2 + (m_2 - m'_2) r,$$ of which there are at most two possibilities, one of which is necessarily zero and the other of which you can probably find in your head by this point.*  The same goes for longer messages with more work and more roots to sift through.  Exactly the same analysis applies to GHASH, which like Poly1305 is a polynomial evaluation hash; similar analysis will tend to apply to other universal hash families.

But the nice thing about Poly1305—or any suitable choice of universal hash family—is that the probability of this event is negligible, well below $2^{-100}$, which is good news for the composition as a candidate PRF, and thus also as a candidate MAC.

In particular, suppose the PRF-distinguishing advantage of any adversary against $F$ is bounded by $\varepsilon_F$, and suppose the hash family $H$ (e.g., Poly1305, GHASH, etc.) has collision probability bounded by $\varepsilon_H$.  Then PRF-distinguishing advantage of any adversary making $q$ oracle queries against $m \mapsto F_k(H_r(m))$ is bounded by $\varepsilon_F + \binom{q}{2}\varepsilon_H$ (proof).

Thus this technique is a good way to build a long-input, short-output PRF out of a short-input, short-output PRF and a universal hash family.  This structure is used by, for example, AES-GCM-SIV.

* Strictly speaking, there may be more possible values of $r$ because the polynomial evaluation giving an integer representative in $\{0, 1, 2, \dots, 2^{130} - 2\}$ is further reduced mod $2^{128}$ to make the Poly1305 authenticator.  But this only multiplies the possibilities by a small number, at most 4.


Variant of the Decisional Bilinear Diffie Hellman problem

Your problem is stronger than the DBDH problem because any oracle that responds to your query can also respond to DBDH. I think that you must try to reduce this problem to DDH. This means an input $(e(g,g),P=e(g,g)^x,R=e(g,g)^y,Q)$ and the decision whether $Q=e(g,g)^{xy}$.


What is the relationship between attribute based encryption (ABE) and access control?

ABE provides a secure and automatic way to enforce access control, but access control may not involve encryption.

In the ABE setting, the resources (that one wants to access) are encrypted by a "controller" and then the ciphertexts are made public and each user is granted a key corresponding to its specific access right. Then, the controller doesn't need to interact with the users to manage their access, because such access control enforcement can be guaranteed by the security of the underlying encryption scheme.

However, in a general access control setting, a "controller" (e.g., an OS or an application) may need to interact with the user (e.g., via an OS access control mechanism or a login system) and grant it the correct access right each time the user wants to access some resources. The resources here may not be encrypted, but are only available to the "controller".


Your confusion comes in who the client's nonce is protecting. The client's nonce protects the client from server replays. Similarly, the server's nonce protects the server from client replays. This makes it so that neither has to remember past nonces. As long as the client is implemented correctly and does not reuse a nonce, a server trying to replay a message will fail.


Is the difference distribution table of AES S-box uniform?

The difference distribution table for the AES s-box contains mostly probability 2/256 differentials. However, there is a single probability 4/256 for each input/output difference. I uploaded a dump of the table here so that you can see.

The code used to produce this table can be found here. Disclaimer: This is my personal github.

If by "uniform", you mean all values equal, the case is no. If you meant "differential uniformity", that is a term with a precise meaning:

From this paper, they define differential uniformity as "A mapping is called differentially uniform if for every non-zero input difference and any output difference the number of possible inputs has a uniform upper bound".

The AES s-box is a differential 4 uniform function


What does the〈 〉notation mean in this situation?

From the context of the exercise, it appears that $\langle x\rangle$ is meant to denote a canonical representation of the integer $x$ as a bitstring of length $n$.

If this were not the case, those inputs and outputs would not be in the correct  domain and range respectively.

Likely this notation was defined somewhere in the lecture notes, but I cannot find them at the moment.


About the security of GnuPG private key on-disk storage

It is likely secure, yes, when it comes to SHA-1.

The S2K function, as you mention, simply repeatedly inputs the 8-byte salt and encoded passphrase  into the ongoing hash function until a certain number of bytes has been processed (the work factor for this function). Then it produces a key that is smaller than the hash output size.

Now this output is an AES key, and we can assume that this key cannot be retrieved, nor is it stored. As you control the salt and secret key, it is impossible to use the collision weakness of SHA-1: even a collision in the output of S2K would be useless. Similarly, a pre-image attack on S2K is useless as well, as the output of the S2K hash is simply not available.

The only possible issue could be that SHA-1 is shown to have such short cycles that multiple inputs could produce the same S2K output. In that case it might be easier to find a matching input, as multiple input values would match. But there is the salt, the relatively short password, the high cycle size of SHA-1 etc. that makes this highly unlikely; this is really grasping at straws.

That all said, S2K is far from perfect. SHA-1 is easy to put in hardware (if it is not already there in current CPU's), S2K doesn't use memory to make e.g. hashing password on a GPU or other specialized hardware tough.

The biggest weak point is and remains the password. I'd rather spend my time making sure that the user is pushed really hard to use a strong password. Because if the password is much smaller than 50 bits then all the cryptography in the world is not going to matter.

Dictionary / brute force attacks on the password will always be more efficient, basically. Spend your time avoiding those.


Why does the crypto_box functionality in NaCl library exposes the nonce to the programmer

The article on NaCl by its authors touches this subject. I'll quote here the relevant bit:

Nonces. The crypto_box API leaves nonce generation to the caller. This
is not meant to suggest that nonce generation is not part of the
cryptographer’s job; on the contrary, we believe that cryptographers
should take responsibility not just for nonces but also for other
security aspects of high-level network protocols. The exposure of
nonces simply reflects the fact that nonces are integrated into
high-level protocols in different ways.
It might seem simplest to
always generate a random 24-byte nonce n, and to transmit this nonce
as part of the authenticated ciphertext; 24-byte random strings have
negligible chance of colliding. If ciphertexts are long then one can
tolerate the costs of generating this randomness and of expanding each
ciphertext by 24 bytes. However, random nonces do nothing to stop the
simplest type of forgery, namely a replay. One standard strategy to
prevent replays is to include an increasing number in each packet and
to reject any packet whose number is not larger than the number in the
last verified packet; using these sequence numbers as nonces is
simpler than giving each packet a number and a random nonce. On the
other hand, choosing public nonces as sequence numbers means giving
away traffic information that would otherwise be somewhat more
expensive for an attacker to collect. Several different solutions
appear in the literature; constraints on nonce generation are often
tied directly to questions of the security and privacy that users
expect.
Current applications of NaCl, such as DNSCurve and CurveCP,
have different requirements regarding nonces, replays, forward
secrecy, and many other security issues at a higher level than the
crypto_box API. A nonceless API would require higher-level
complications in all of these applications, and would not simplify
their security analysis.


Does it use KDF (key Derivation function)? If yes, then is the KDF capable of decreasing the size of bits too?
...how is DES able to convert this (80 bit) key into a 64 bit one?

AES and DES do not perform this task. The specification states that AES uses two sequence of 128 bits as input.
"key" means "cryptographically strong bits".
Something like APPLE PIES is a password rather than a key.

how is it able to upscale/downscale it to lower bits in order to feed it to the algorithm. Does it uses KDF (key Derivation function)? If yes, then is the KDF capable of decreasing the size of bits too?

The key derivation process may involve multiple invocations and iterations to generate output larger then the output size of the hash function, and the application may truncate keys down to the correct size when necessary.
How to derive a key from a password
This question has already been asked: see this answer.
A KDF is used to turn a password into a suitable key, but this is a separate process that is not performed  by the AES/DES algorithms.


Why is RSA encryption version 1.0 not specified in an RFC?

RSA is and was specified by the PKCS#1 specifications of RSA laboratories. PKCS are the "Public Key Cryptography Standards" by RSA Laboratories, now part of EMC2. The RSA PKCS#1 v1.5 is the lowest publicly released version of RSA by RSA labs that can currently be downloaded.

Version 1.0 to 1.4 are working drafts as specified in the PKCS#1 documents themselves and at least the inital PKCS#1 RFC 2313 as well:

Versions 1.0–1.3 were distributed to participants in RSA Data Security, Inc.'s Public-Key Cryptography Standards meetings in February and March 1991.
Version 1.4 was part of the June 3, 1991 initial public release of PKCS. Version 1.4 was published as NIST/OSI Implementors' Workshop document SEC-SIG-91-18.

Although the RSA standards have been defined by RSA Laboratories they are likely to have been influenced by the participants to the meetings and workshops.

The RFC's are simply a reiteration of the PKCS#1 standards that have undergone public scrutiny. They are not in control by a single private party. So the standard may be identical, but it is at least open. In general the RFC's just keep to the PKCS#1 specifications, but at least in principle follow up documents may deviate from the specifications by RSA.


Determining a cryptographic algorithm by description

It's RSA signature validation, using the PKCS-1.5 signature padding, with $e=3$, and the RSA modulus given by $\mathit{key}$.

It's a circa 1024 bit key; assuming $\mathit{key}$ is a properly chosen RSA modulus, nowadays it would be considered potentially breakable (in the sense that you could recover the private key, and hence be able to sign any message you want), however it would be a major effort.

If you're asking whether you can trust it, well, probably not; a well funded adversary could likely break it.  If you're asking whether you can break it, well, no; you're not a well funded adversary.


How to recognize Authenticated Encryption with Associated Data ciphersuites

Can you help me identify the ciphersuites that provide Authenticate
  Encryption with Associated Data (AEAD) from those that do not?

All which explicitely name gcm or chacha20_poly1305 are AEAD ciphersuites. The others use the TLS default which is MAC-then-encrypt with CBC.

  Is it always the case that AE ciphersuites must be also Forward
  Secrecy ciphersuites?

There's no technical reason that forces this to be the case. In fact RFC 5487 defines TLS_PSK_WITH_AES_128_GCM_SHA256 which uses AES-GCM (AEAD) but doesn't offer forward-secrecy. And if you don't accept a PSK suite as an answer here, RFC 5288 defines TLS_RSA_WITH_AES_128_GCM_SHA256, which uses RSA key-transport (and thus offers no forward secrecy).

However, AEAD is what some people call "modern crypto". And as such it is usually paired with other "modern crypto", which does usually mean that you prefer to use forward-secrecy with AEAD suites and only have the non-forward secrecy ones for fallback, after all, clients who implement AES-GCM will also have all the other modern crypto like ECDHE.

  Is Authenticated Encryption (AE) is the same AEAD? or they are
  different terms?

Technically yes. An AE scheme only needs to deliver authenticated encryption of the plaintext, the AEAD scheme also needs to authenticate data as well, so every AEAD scheme is also an AE scheme but not the other way around. Practically however, I am not aware of any scheme that is practically used and is AE but not AEAD (and even then, conversion would be quite simple).


Where I can find a list of certified software / hardware RNGs compliant to NIST SP 800-22?

Please refer the document at NIST site pointing to the document (800-22-rev 1a ) updated on April 2010  (http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf).

The list of special published (SP) documents are available at (http://csrc.nist.gov/publications/PubsSPs.html)

It involves some reading, but should get your answers. Since it will keep changing wouldn't paste an answer here.


AES CBC: Use hash of key as IV when every key is unique?

Yes, that would be an excellent idea, at least if you use a cryptographically secure hash that has output indistinguishable from random. That's however true for most secure hash algorithms out there. You could - for instance - use SHA-256 and then take the leftmost 128 bits; using the leftmost bits is more or less the industry standard.

You cannot derive the key if the IV gets known because the hash is one way, and an adversary cannot predict the IV because to do that the key should be known. One possible issue is that hash algorithms are not always protected against side channel attacks. Then again, most hash algorithms are not directly susceptible to them either.
Beware that you should document that the resulting IV is static, if you ever start reusing the keys then you'd be in trouble.

Alternatively you could use a KDF to derive two values from a master secret, say S. For instance, you could use K = KDF(S, "Key", 128) and IV = KDF(S, "IV", 128) to derive both the encryption key and the IV from one input value.

K | IV = KDF(S, "KeyAndIV", 256) is also often used - it is for instance similar to key derivation in TLS 1.2. This is provably secure and may require less computation time than doing the KDF twice.

The resulting key and IV when using a KDF over a secret value do not depend on each other. This is more secure than having the IV being dependent on the key. A good KDF for key based key derivation (KBKDF) is HKDF.


Could Riemann hypothesis solve certainly RSA?

It's not that proving the Riemann Hypothesis would itself lead to a breakthrough against RSA.  Rather, it's speculation that the methods leading to the discovery of a proof of the Riemann Hypothesis could lead to a profound discovery about prime numbers that, say, makes factoring easy.

The reason that proving the Riemann Hypothesis in itself has no bearing on RSA's security is that we can simply accept it as true now.  We don't need to wait for a proof to use the Riemann Hypothesis to find holes in RSA.  If we found a way to use the (apparent) fact that all nontrivial zeros of the zeta function have real part $\frac 12$ to crack RSA, and this crack actually worked, then it simply doesn't matter whether the Riemann Hypothesis was proved.


What are the negative consequences for choosing 8 S-boxes for DES vs 1 S-box for AES?

Implementation complexity in software and constrained hardware.

In Serpent, each round uses the same S-box, even though 8 s-boxes are used. This makes it easier to bitsplice the cipher, or process each 4-bit s-box in parallel.

The minimum gate count for a DES implementation is 2300 gates. For Present it is 1075 gates.

Software and constrained hardware implementations benefit from a cipher that can be easily serialized.

Hash Functions and RFID Tags: Mind the Gap


Can we design a public-key infrastructure without certificate authorities?

There was a post on security.stackexchange last week about this. SSL/TLS with Certificate Authorities for all intents and purposes is now completely insecure from governments and any organisation who has a CA pre-trusted inside the standard web browsers.

DNSSEC will also fall under the same scenario because at the top level you have a particular government in control of the DNS root.

There is one design that may help solve the issue. There's also an excellent talk explaining the issue with Certificate Authorities. At about 35 mins he discusses the problems with the Perspectives Project and recommends another solution called Convergence. I would recommend everyone moves to something like that as a matter of urgency.


What's a good P to use in ElGamal key generation?

With most finite field crypto using a standard group is no problem. I think ElGamal encryption doesn't have any specific requirements for group or generator that plain Diffie-Hellman doesn't have.

So you could look into RFC 2409  Internet Key Exchange or RFC 5114  Additional Diffie-Hellman Groups for Use with IETF Standards for groups.

AFAIK ElGamal signatures have some additional requirements for the generator, so the above groups are probably a bad idea. But I wouldn't use ElGamal signatures in the first place, preferring DSA or Schnorr.


identity based cryptography (IBE) without key escrow

It's not possible to completely get rid of the PKG, but one can limit the amount of trust on a (single) PKG through distributed key generation --- see BF01,§6. On the other hand, one could hold the PKG accountable in case it behaves malicously --- see Goy07.


The poblem of computing the private key $d$ from the public key $Q$ is indeed referred to as $ECDLP$. It is crucial that you choose the domain parameters so that the $ECDLP$ is intractable. Concerning your choice of $d$ ... it is too small and can thus be computed efficiently. Imagine $d$ not having 7 Bits like in your example but 192-, 384- or even 512 Bits. You wouldn't get very far using your method (or any other currently known and implementable algorithm).

In order for the $ECDLP$ to be intractable, $d$ must be adequately chosen so that you cannot just brute-force all values for $d$ until you find a $d$ so that $dP = Q$. This is why curves that are considered as secure today use large values for $n$ and $p$ and create a random value $d$ in the range $[1\dots n-1]$.


How to solve Columnar Transposition Cipher without a key

I wrote an answer to a related question earlier showing an example of how to break a columnar transposition cipher by hand.  The basic steps are two-fold:

Test different key lengths, and look for a length where the letters in each column look like they might plausibly be consecutive.
Once you've picked a key length, shuffle the columns around until they start to line up into meaningful fragments of text.

In the linked example, these steps are made easier by knowing a distinctive word that appears in the plaintext, and specifically the fact that the ciphertext contains a single Q and a single U, which are almost guaranteed to be consecutive in English text, but the same general method can be used even in the absence of such clues.

It would probably be possible to automate this process using a stochastic optimization algorithm like randomized hill climbing: basically, pick a random initial ordering for the columns, calculate how similar the resulting plaintext looks to English (using $n$-gram frequency statistics), and then repeatedly try to move one or move consecutive columns around and see whether this makes the plaintext look more like English.  If it does, make the change and keep trying to improve it further; if not, reject the change and repeat.

For 7 columns, just trying all the 7! = 5040 possible column orders would also be feasible for a computer, although the number grows rapidly as the number of columns increases.  As noted, generating all possible permutations of the columns is a standard computations problem, for which several well known algorithms exist.


Why do $p$ and $q$ have to be different in RSA?

Because factoring $n$ where $n=pq$ and $p=q$ is really, really easy, take a square root. If you can factor $n$, you can break RSA. Therefore, having $p=q$ is detrimental to the security of RSA.


AES CBC mode or AES CTR mode recommended?

I wrote a rather lengthy answer on another site a few days ago. Bottom-line is that CTR appears to be the "safest" choice, but that does not mean safe. The block cipher mode is only part of the overall protocol. Every mode has its quirks and requires some extra systems in order to use it properly; but in the case of CTR, the design of these extra systems is somewhat easier. For instance, when compared to OFB, there is no risk of a "short cycle" with CTR.

This is why actually usable modes like EAX and GCM internally use CTR.


Why aren't stream ciphers extremely secure?

Yes, stream cipher is to OTP what CSPRNG is to true randomness.

Yes, breaking a stream cipher implemented with CSPRNGs XORed together (each independently seeded) demonstrably implies breaking each CSPRNG (or a side channel).

Yes, there has been less than perfect stream ciphers/CSPRNGs around. I guess that's for a large part because of efficiency concerns, and because their security was adequate for many of the intended uses (RC4 was designed with performance in mind, like 30 years ago; the first commercial use I saw of it was real-time decryption of Adobe Type Library fonts distributed encrypted on freeby CD-ROMs, with each font category unlocked by a 40-bit key).

I guess that we nowadays use single-CSPRNG stream cipher (like AES-CTR, Salsa, ChaCha..) because simplicity and speed are virtues. They are believed extremely secure, except for implementation attacks (penetration of platform, side channel).


A slightly more efficient method to perform decryption would be:

Compute $r^e = (y^d)$
Find the multiplicative inverse $r^{-e}$ of $r^e$ modulo $n$
Compute $m = (r^{-e} \cdot z)^d = (r^{-e} \cdot r^e \cdot m^e) ^d$

This has two computations of $x^d$ for some $x$; your method has three.

On the other hand, this doesn't address your question; if $r^{-1}$ doesn't exist, neither will $(r^e)^{-1}$.

For your question, well, there is no such "better" algorithm, because the decryption is inherently ambiguous.

Suppose that $n = pq$ (where $p$ and $q$ are distinct primes), and you selected a value $r = kp$ (for some integer k).  Then, if we consider two distinct messages $m_1$ and $m_2$ with $m_1 = m_2 \mod q$, and the encryption of both these messages with that same $r$.  They share the same $y$ value (because $y$ depends only on $r$), and as for the $z$ value:

$z_1 = (r \cdot m_1)^e \mod n$

$z_2 = (r \cdot m_2)^e \mod n$

we see that:

$(z_1 - z_2) \bmod p = r^e \cdot (m_1^e - m_2^e) \bmod p = 0$  (because $r$ is a multiple of $p$

$(z_1 - z_2) \bmod q = r^e \cdot (m_1^e - m_2^e) \bmod q = r^e \cdot 0 = 0$ (because $m_1^e$ and $m_2^e$ are the same modulo q)

and hence (by the Chinese Remainder Theorem), $z_1 = z_2 \mod n$

So, if you attempt to decrypt the message $(y, z_1)$, there are at least two valid decryptions ($m_1$ and $m_2$), and no algorithm can distinguish which is meant.

If you prefer a concrete example, consider the case where $p=5$ and $q = 11$.  We can select $e = 3$ and $d = 27$ (actually, $d=7$ would work just as well).  Then, if we select $r = 10$ and $m_1 = 2$ and $m_2 = 13$, then the encryption of $m_1$ would be:

$((10^3)^3, (10\cdot2)^3) = (10, 25)$

and the encryption of $m_2$ would be:

$((10^3)^3, (10\cdot13)^3) = (10, 25)$

Hence if we get the ciphertext $(10, 25)$, we can't tell if the original message with 2, 13, or even a bunch of other values (24, 35, 46)

Now, in practice, this is not likely to be a concern; the probability of this happening with a random $r$ is about $1/p + 1/q$; if $p$ and $q$ are large enough to make factorization difficult, this failure probability is negligible.

BTW: why are you considering this method, rather than a more straightforward RSA-based approach?  If it is to get some homomorphic properties, well, it doesn't hide the encryption of 0 very well, and that's really what we would like in a multiplicative homomorphic encryption.


Benchmarks for second round CAESAR competitors

Benchmarks for 2nd-round candidates are now available at the eBACS website. There is also an independent report comparing candidates' performance.


How can Alice enable Bob to look-up values in a private map

Many (most?) leading PSI protocols can be easily adapted to provide this functionality. It is sometimes called "PSI with associated data" or "PSI with data transfer". For example, you can see this variant of PSI described explicitly in:

Emiliano De Cristofaro and Gene Tsudik. Practical private set intersection protocols with linear complexity. Financial Cryptography 2010.

Even many protocols which don't mention "associated data" explicitly can be easily modified to provide it. I know for sure that the following papers (which are the fastest 2-party semi-honest PSI) will support it:

Benny Pinkas, Thomas Schneider, Gil Segev, Michael Zohner: Phasing: Private Set Intersection using Permutation-based Hashing. Usenix 2015.
Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, Ni Trieu: Efficient Batched Oblivious PRF with Applications to Private Set Intersection.
CCS 2016.

These protocols use an "oblivious PRF" paradigm for PSI, which works roughly like this:

Parties perform an Oblivious PRF where Alice learns (description of) a random function $F$ and Bob learns $F(y)$ for every $y$ in his set.

Alice can compute and send $F(x)$ for every $x$ in his set. Now Bob can compare against his set of $F$-values and identify the intersection. For values $x$ that Alice has but Bob doesn't have, the corresponding $F(x)$ value looks random to Bob, so leaks no information about that $x$.

There is a fair amount of other algorithmic/combinatorial stuff in these protocols, but eventually at some level the protocol is doing what I described above.
To add associated data to this protocol outline, you can just use the $F(x)$ values as keys to encrypt the associated data. Something like this:

For every $y$, Bob has $F(y)$ and (if it's not long enough) expands it with a PRG to get two values $tag_y$ and $k_y$.

For every $x$, Alice similarly expands $F(x)$ into $tag_x$ and $k_x$. She sends $(tag_x, \mathsf{Enc}(k_x, data[x]))$, where $data[x]$ is the record/data associated with key $x$.

Bob can look for tuples of the form $(\tau, c)$ where $\tau$ is a tag that he recognizes as $tag_y$. He can then decrypt $c$ with the corresponding key $k_y$ to obtain the data associated with $y$.


Finding a pair of exponents so that $c^a \bmod N = c^b \bmod N$

If you find such you can break RSA.

Assuming the order of c is maximal(likely if c is random ciphertext).
If we have such distinct exponents  and  they must be equal mod $\lambda(n) = lcm(p-1,q-1)$.

Let the difference between the exponents be $f=b-a$, $f=0\space mod \lambda(n)$

We pick a value e coprime with e, pick a small prime and verify.
We will then calculate $d = e^{-1} mod f$

We can then find the factorization of N using the algorithm described: https://www.di-mgt.com.au/rsa_factorize_n.html

So no, if you do not know the factorization of $n$ you can't find such an exponent pair.

Example:

N= 25777 //from link
c= 1517 //randomly chosen
a = 111 //less randomly chosen(I picked)
Possible b are: 6475,12839,19203,25567 we will pick the last one
this gives us f=25456
We try e=3 and verify indeed gcd(e,f)=1
We use extended eucleadean algorithm to find d=16689 and this is exactly the value used in the above link to factorize n.

If we pick b=19203
we get f=19092 and e=3 doesn't work so we will pick e=5
We get d=7637

we follow the algorithm linked
k=de-1 = 38184

We try several g, skipping to g=5
t=k=38184
g^t % n = 1
t=t/2 = 19092
g^t % n = 1
t=t/2 = 9546
g^t % n = 15050
and we check gcd(15050,n) = 149

We found a non trivial factor of n. Q.E.D

Edit 2: Fgrieu comments the proof above does not hold in the general case. For some N the first assumption of high order may not be sound, and for very large b-a the last algorithm may not be efficient. I do not know how to rectify these. Which means though this "proof" should still be sufficient evidence that the original problem in the question of finding such a pair a,b is indeed very hard. Yet this is not a solid reduction between that problem and factorization in the general case.


Suppose we live in a work where $\mathsf{P}\neq\mathsf{BPP}$ - that is, there exists problems which can be solved in randomized polynomial time, but not by any deterministic polynomial time algorithm. In such a word, if we define a OWF as a function which is hard to invert for deterministic polytime adversaries, we might in fact have no real guarantee for its security: in the real world, it's not so hard to generate random bits (say, using some appropriate quantum device). Hence, there could exist an attack which works well in the real world, using a source of random bits, even though the OWF might be secure against all deterministic adversaries. Hence, such a definition would not capture correctly the class of functions which allow for secure cryptographic applications.

Note, however, that it is widely believed that $\mathsf{P} = \mathsf{BPP}$. Indeed, this follows from some worst-case circuit lower bounds (or equivalently, the existence of some strong form of pseudorandom genarator): if there exists problems in $\mathsf{DTIME}(2^{O(n)})$ which have circuit complexity $2^{\Omega(n)}$, then $\mathsf{P} = \mathsf{BPP}$.


It might help if you explain what problem you're trying to solve.

For example, what exactly do you mean "Key1 = Key2|Key3"?  If you mean (say) taking a 256 bit AES key, and splitting it up into two halves (where you need to present both halves to encrypt/decrypt), well, that's easy; however, I doubt that's what you're asking.

Alternatively, when you say "Key2|Key3", you might be asking to split the key into two halves; where Bob has one half (and performs the operation on it), and Carol has the other hand (and she takes Bob's result and her own key, performs the operation on it, and her result is exactly what Alice got with the original key.  If so,  we can consider (for example) 2AES; that is, you encrypt the message with AES key 1, and then with AES key 2.  So, the full key can be considered AES key 1 concatenated with AES key 2; obviously, we can split it into two halves.  However, I suspect that this won't address your problem (whatever it is) either.

Assuming that the second guess was on the right track, and you insist that the operation on key 1 are exactly the same as the operations on key 2 and key 3, well, we run into a problem.  Generally speaking, symmetric ciphers aren't closed operations; there usually aren't any key 2's and key 3's which are jointly perform the same operation as key 1.  However, one example does come to mind: Pohlig-Hellman; with that, given a key, you really can split it randomly into two keys.  However, I again can't be quite certain if that's what you're looking for either.


If the goal is to distinguish the encryptor from random, the obvious thing to do is to ask for $\sqrt{2^{15}}$ encryptions of the same plaintext.  Assuming that each encryption uses one of the $2^{15}$ allowed IVs randomly, then with good probability, two separate encryptions will use the same IV (and thus result in the exact same ciphertext).  This is rather better than the $\frac{1}{2^{15}}$ result you get from trying to predict the IV.

Now, if you want something better than a distinguishing attack, well, consider this attack model: the attacker has a ciphertext block $C$ where he has partial information about the corresponding plaintext $P$, namely, he knows the initial 113 bits, and has no information about the remaining 15.  The attacker wishes to recover the remaining 15 bits, and is able to inject chosen plaintext, and is able to see in the ciphertext the IV that the encryptor selected.

What the attacker can do is inject a series of chosen plaintexts with the first 113 bits being the plaintext $P$ he knows, and the last 15 bits being 0 (arbitrary works, 0 makes it a bit easier to explain).  The encryptor will select a random IV; if the random IV he selects happens to have the exact same last 15 bits as the unknown plaintext, then the resulting initial ciphertext block will be the challenge ciphertext block $C$ (and so, by examining the IV that the encryptor used, the attacker now knows the value $P$).

For each submitted plaintext, there's a probability $2^{-15}$ of the random IV being 'right', and so this takes an expected $2^{15}$ plaintext queries to succeed.

In contrast, in this attack model, if we assume that the attacker can predict the entire IV, he could recover the plaintext with an expected $2^{15}/2$ queries, and so the attacker not knowing the last 13 bits only reduces the efficiency by a factor of 2.


Can one have an authentic, but repudiable, message without a previously shared secret?

There's an obvious solution using DH: Alice has a private key $a$ and a public key $g^a$; Bob has a private key $b$ and a public key $g^b$.

When Bob sends a message, he computes the shared secret value $(g^a)^b$, converts that into a MAC key (possibly using a nonce to prevent key reuse), computes the MAC of the message, and sends the message and the MAC (and any nonce) to Alice.

When Alice receives the message, she computes the shared secret value $(g^b)^a$, converts that into a MAC key, and verifies the MAC.

Now, Eve cannot modify the message, because she doesn't know the MAC key, because she can't solve the DH problem based on the public keys $g^a$ and $g^b$.

Alice can validate that the message was sent by Bob.  However, she can't prove it to anyone else, even if she were willing to expose her private key, because she is just as able to generate that message as Bob was.


converting to rank one constraint system

what does he mean by saying " There is a standard way of converting a logic gate into a (a, b, c) triple depending on what the operation is " ?

He means that every "+" operation will follow the same pattern.  (As will every "-" operation, "*" operation, and "/" operation)
Example using '+' operation:
Statement:
x + y = z

Witness vector
Let's assume our witness vector corresponds to the following variables:

[ ~one, x, y, z (or ~out) ]

The order of these variables is arbitrary, it just has to be kept consistent through out the process
Convert the statement into the A * B - C = 0 format:
(x+y) * 1 - z = 0

This means the following is also true:
A = x + y
B = 1
C = z

Determine the "factors" for each variable in our witness vector
A = (0 * ~one) + (1 * x) + (1 * y) + (0 * z) = x + y
B = (1 * ~one) + (0 * x) + (0 * y) + (0 * z) = ~one
C = (0 * ~one) + (0 * x) + (0 * y) + (1 * z) = z

Our vectors then directly correspond to the factors for each variable in the witness vector
A = [0, 1, 1, 0]
B = [1, 0, 0, 0]
C = [0, 0, 0, 1]

Note that this "pattern" of vector will be used for ANY addition gate where two variables are being added to create a third variable.

A:

1 for each value corresponding to the variables being added
0 for everything else

B:

1 for the value corresponding to ~one
0 for everything else

C:

1 for the value corresponding to the output variable
0 for everything else

I hope this also demonstrates why the ~one variable is necessary.

EDIT:

why 3 vectors ? and HOW does that exactly work ?

The formula A.s * B.s - C.s = 0 allows you to perform any addition/subtraction/multiplication/division operations between values and variables.
The dot product (A.s) allows for scaling and addition of values, and the A*B part allows for multiplication and division of values.
The C vector simply represents the result as a value or variable


Why is a 1 added after the message input and before adding padding zeros (if necessary) when using SHA256 or RIPEMD160?

If you look at the Wikipedia on padding article page, you will see many different ideas.

The main problem when designing a padding, firstly, one has to consider how to eliminate the padding correctly, all the time. It is the designer's choice, as noted in and the original RFC 4634 -- SHA and HMAC-SHA.

Once you put 1 followed by many 000 to the end of a string, you can remove the padding by looking the first position of a single 1 from the end. That was the simplest idea for padding, AFAIK.

When considering that hashes only supply integrity, If finding a collusion is easy with this (or any) padding than the hash is already failed there.


What is the difference between cfb and cfb1 and cfb8 ? ( like openssl's aria-128-cfb & aria-128-cfb1 & aria-128-cfb8 )

What is the difference between cfb and cfb1 and cfb8?

Well, first of all, we need examine what CFB is.  Here is what the encryption process is:

Take the previous $n$ bits of ciphertext (where $n$ is the block size of the cipher, for Aria, $n=128$
Send it through the block cipher in encryption mode
Extract $k$ bits of the result, exclusive-or that with the next $k$ bits of block text, and make that the next $k$ bits of ciphertext.

That's it.  Each iteration of the loop encrypts $k$ bits of plaintext, generating $k$ bits of ciphertext, and performs one block cipher operation.

And, to answer your question:

For cfb1, $k=1$
For cfb8, $k=8$
For cfb, $k=n$ (or 128 for Aria)

Of course, you might ask "why in the world would anyone use cfb1?  To encrypt 128 bits, it runs Aria 128 times, that's dreadfully inefficient"

The answer is "in case the ciphertext might be accidentally corrupted by bit insert or deletions".  The original idea was that CFB was targeted toward encrypting traffic going over serial interfaces, such as RS-232 or Bisync.  Now, RS-232 has the property that, due to line noise, an additional character might be received, or a transmitted character might be dropped (Bisync might have that same property with bits; I've never worked with Bisync, so I'm not certain).  Now, if we consider using CBC mode to encrypt the traffic, well, after such a character insert/delete error, the blocks used by the encryptor and decryptor will not match up, and so the decryptor will get gibberish (and it will continue to get gibberish long after the error).  In contrast, with CFB8, the next 16 characters will be decrypted incorrectly; then, as long as no further errors occurred, the decryption will proceed correctly.  CFB1 has the advantage that it can do with individual bits being inserted or deleted.

Of course, all that is historical.  Today, we generally are more sensitive to the issues that an adversary can cause by deliberately introducing error.  Because of that, we generally want to discard traffic which might be decrypted incorrectly, rather than passing it on (and so the error nonpropogation properties of CFB as not as attractive).


Decrypting files with an unknown method but a known result

No, don't assume it is RSA as it likely isn't based on the information.

You already have a possible block length. 64 bit block length could mean DES (or one of its variants such as 3DES) or blowfish. Another possibilty is that there was an 8 byte pad used in repeated XOR fashion. I'm sure there are other possible block ciphers with 8 byte block size.

Next I would look for repeated blocks. Anywhere in the plaintext file where the data is the same, see if the ciphertext data is the same. This would suggest either repeated XOR or ECB mode. If this is not the case, other modes (CBC, etc) are likely. The absence of repeated cipher blocks (where there are duplicate plaintext blocks) would seem to eliminate repeated XOR.

If that is all the information you have, your next step would be to brute force. If repeated XOR is a possibility, and since you know the header is 00 00 ..., the ciphertext would be your XOR pad. So try that and see if the decrypted file looks as you would expect.

Otherwise, I'd start with DES as it is probably the more popular of the two ciphers.


Possible to use an accumulator to "license" or restrict the qty of certificates being used?

In short:  The parent CA would sign the public key of an n-time signature scheme, as opposed to the public key of a signature scheme which is valid for an unbounded number of signatures (the current design).

n-time signature schemes are usually just constructed by generating n instances of a one-time signature scheme and then accumulating their public keys together into one public key.

The child CA would present their n-time public key (along with a proof that the public key accumulates only n OTS instantiations) to the parent CA to be signed, just like usual.


In this context 'security margin' is a measure for how much better we need to get at analyzing a cipher to break it. Such advances in cryptoanalysis require new ideas of how one might attack a cipher. Thus estimating how strong a cipher is, is hard.

Ultimately we can only tell something is broken, after we've broken it.

We typically look at a few properties to estimate the security margin:

How much effort was put into analyzing this cipher?

AES has seen a lot, finalists in a popular competition (Serpent etc.) have seen quite a bit, but less than AES, and some random guy's cipher has probably seen almost no effort at all.
How well do we understand it?

We have a decent understanding of certain block-cipher constructions with a clear iterated round structure. But we might not understand some new innovative cipher very well.

For example NIST eliminated some candidates in the SHA-3 competition because their design was unusual and not understood very well.
How many rounds are broken so far?

For example a cipher where we've broken 2.5 out of 10 rounds is probably stronger than a cipher where 60 out of 80 rounds are broken if we understand both of them equally well.

Ciphers with a clear round structure are often preferred. Typically breaking more rounds becomes a lot harder, and it provides at least some way to quantify how much progress was made in breaking the cipher.

Lack of clear round structure makes sudden breaks more likely.

So if we put a lot of effort into analyzing some cipher, think we understand it well, and still only broke a few rounds, then we believe the security margin is large.

Resistance to brute-force can be easily quantified, estimating resistance to cryptoanalysis is full of guesswork and pretty subjective. So it's not surprising that you only find pretty vague statements.


Implement the joint-feldman DKG algorithm

You can look up at the Kyber library, in the package share, there is a the Feldman version as well as the Rabin version.
You can later on use this to make distributed schnorr signatures or TBLS signatures. You can lookup  these types in the sign package.

PS: I'm one of the authors of these libraries. Happy to help if you have any questions :)


The bit interleaving code looks like this:

{
    const UINT32 * pI = (const UINT32 *)in;
    UINT32 * pS = state;
    UINT32 t, x0, x1;
    int i;
    for (i = laneCount-1; i >= 0; --i)
    {
        x0 = *(pI++);
        t = (x0 ^ (x0 >>  1)) & 0x22222222UL;  x0 = x0 ^ t ^ (t <<  1);
        t = (x0 ^ (x0 >>  2)) & 0x0C0C0C0CUL;  x0 = x0 ^ t ^ (t <<  2);
        t = (x0 ^ (x0 >>  4)) & 0x00F000F0UL;  x0 = x0 ^ t ^ (t <<  4);
        t = (x0 ^ (x0 >>  8)) & 0x0000FF00UL;  x0 = x0 ^ t ^ (t <<  8);
        x1 = *(pI++);
        t = (x1 ^ (x1 >>  1)) & 0x22222222UL;  x1 = x1 ^ t ^ (t <<  1);
        t = (x1 ^ (x1 >>  2)) & 0x0C0C0C0CUL;  x1 = x1 ^ t ^ (t <<  2);
        t = (x1 ^ (x1 >>  4)) & 0x00F000F0UL;  x1 = x1 ^ t ^ (t <<  4);
        t = (x1 ^ (x1 >>  8)) & 0x0000FF00UL;  x1 = x1 ^ t ^ (t <<  8);
        *(pS++) ^= (x0 & 0x0000FFFF) | (x1 << 16);
        *(pS++) ^= (x0 >> 16) | (x1 & 0xFFFF0000);
    }
}

There is also the matching deinterleave code in the extract function.

I also wrote a Keccak/SHA3 class using that code (or something similar) as a base. For whatever reason I did not like the way that looked, and ended up writing my own, which ended up being 1.45X faster (just the interleave, not the hash) when compiled compared to my implementation of this interleave code, so there are faster ways to do it.

I also found it is easier to interleave/deinterleave the entire state during dev/testing when you absorb or extract as you can view intermediate values of the state working variables and compare to a reference implementation.


Is CBC mode encryption vulnerable to a reordering attack?

Yes.  Assume that the attacker knows the ciphertext $c = c_1 \mathbin\| c_2$, the initialization vector $v$ and the plaintext $m = m_1 \mathbin\| m_2$.  This tells them that

$D_k(c_1) = m_1 \oplus v$ and
$D_k(c_2) = m_2 \oplus c_1$,

where $D_k(\cdot)$ denotes block cipher decryption under the (unknown) key $k$.

In particular, this implies that, if the attacker reverses the order of the ciphertext blocks to produce the modified ciphertext $c' = c_2 \mathbin\| c_1$, then they will know that it will decrypt to $m' = m'_1 \mathbin\| m'_2$, where

$m'_1 = D_k(c_2) \oplus v = m_2 \oplus c_1 \oplus v$ and
$m'_2 = D_k(c_1) \oplus c_2 = m_1 \oplus c_2 \oplus v$.

There should be nothing particularly surprising about this: like all non-authenticated block cipher modes of operation, CBC mode is known to be malleable, meaning that an attacker who can change the ciphertext is also able, at least to some extent, to predict the effects of the changes on the resulting plaintext.  If you don't want that (and you usually don't), you need to use an authenticated encryption mode, possibly constructed by combining a conventional mode like CBC with a secure MAC.

(In fact, a further attack on CBC is possible if, as usual, the initialization vector $v$ is transmitted alongside the ciphertext: in that case, the attacker can change the first block of the plaintext to anything they want, without affecting the other blocks, simply by changing the IV.)


Signature generation and encryption are two different concepts. The fact that both can use the same one way function does not change that fact. In the case of RSA, both signature generation and encryption (as well as verification and decryption) uses modular exponentiation. These are called the RSA primitives. They have however different inputs: one uses the private key, the other the public key.

Signature generation and encryption may relate differently for other one way functions. This is for instance the case for the primitives used for elliptic curve cryptography (ECC). In ECC the primitives used for ECDSA signature generation cannot directly be used for encryption/decryption.

The idea that signature generation and encryption should be seen as different concepts is actually made pretty clear in the PKCS#1 standard (of RSA laboratories): the signature generation primitive is called RSASP1 and the encryption primitive is called RSAEP. They do represent the same algorithm internally.

RSAVP1, the RSA verification primitive is indeed performed with the public key. But it doesn't really decrypt any confidential information. Instead it produces a padded hash. This padded hash is free for anyone to see - anybody may verify the message (in this case the certificate). If you require confidentiality you should encrypt the message and the signature value using a key or keyset where the secret key is known by the receiver.

The padding is validated and the hash is compared with the one computed over the (signed parts of the) certificate. If both the padding and hash are correct then the signature must have been created using the private key belonging to the public/private key pair. This is what establishes the trust.

As long as the private key is managed (held) by the signing party then the signing party must have been involved in generating the signature. This is called non-repubility; the signing party cannot claim that somebody else created the signature.


Is it possible to compute the y-coordinate of a point on SECP256K1, given only the x-coordinate

Given an $x$-coordinate of a point on the SECP256K1 curve, is it possible to calculate the corresponding $y$-coordinate?

Yes, if there exists such $y$ for the given $x$. And, absent other indication, such $y$ can only be found within sign (or equivalently, parity). That limitation is because if $y^2\equiv x^3+7\pmod p$ with $p=2^{256}−2^{32}−2^{10}+2^6-2^4−1$ as in secp256k1 has a solution $y_0$ in $[0,p)$, then $y_1=p-y_0$ also is a solution.
Note: in some cases including secp256k1 as used in Bitcoin, a public key with $x$ and without $y$ (that is, in compressed form) comes with a prefix of 02 if $y$ is even, 03 if $y$ is odd, and that allows to fully recover $y$.
By Euler's criterion, $x^3+7$ has a square root modulo $p$ if and only if $(x^3+7)^{(p-1)/2}\bmod p=1$. That holds for the question's $x$, thus there are solutions.
In the general case, the Tonelli–Shanks algorithm can be used to find modular square roots. Since $p\equiv3\pmod4$, that algorithm reduces to computing $y_0\gets (x^3+7)^{(p+1)/4}\bmod p$ and $y_1\gets p-y_0$. The question's $y$ happens to be $y_1$.
Justification: when we have checked $(x^3+7)^{(p-1)/2}\bmod p=1$, and computed $y_0$ as $(x^3+7)^{(p+1)/4}\bmod p$, the later is such that $$\begin{array}{}
{y_0}^2 &\equiv&\left((x^3+7)^{(p+1)/4}\right)^2 &\pmod p \\
& \equiv&(x^3+7)^{(p+1)/2} &\pmod p \\
&\equiv&(x^3+7)^{(p-1)/2}\,(x^3+7)&\pmod p\\
&\equiv&x^3+7 &\pmod p & \text{since}\;(x^3+7)^{(p-1)/2}\bmod p=1\end{array}$$
thus $y_0$ is a solution to $y^2\equiv x^3+7\pmod p$.

Definitions:
$$\begin{array}{l}
u\equiv v\pmod p&\underset{\text{def}}\iff v-u\;\text{ is a multiple of }\;p\\
u=v\bmod p&\underset{\text{def}}\iff v-u\;\text{ is a multiple of }\;p\;\text{ and }0\le u<p\;
\end{array}$$


Verify a RSA signature using only RSA encryption

The API you are trying to use automatically pads (probably RSAES-PKCS1-v1_5 padding). Instead you require it to verify and remove the padding during signature verification.

If you cannot skip the padding then you cannot use the API. Try and find a library that actually can verify instead. You shouldn't program RSA itself, but in the end it's just an algorithm. As long as you have access to the key - and preferably a big integer math library - you should be able to perform RSA modular exponentiation and verification / removal of the padding yourself.

You cannot just magic away 11 bytes that are added to the plaintext before modular exponentiation. OAEP would pad even more.

You could try and decrypt the signature with the public key and hope that the API detects the public key and performs the verification and unpadding instead itself, but that's a long shot. Note that you should get an error message if the padding cannot be verified.

Note that Diffie-Hellman also performs modular exponentiation. Sometimes you can use DH functionality to "raw decrypt" an RSA signature.


Given one message encrypted repeatedly with the same 'n' but different 'e's, is it possible to decrypt the ciphertext without simply bruteforcing n?

Ok, here's a hint:

Suppose you know the values of $P^{e_1} \bmod N$ and $P^{e_2} \bmod N$.  How could you use those two values to compute $P^{e_1 - e_2} \bmod N$?  How could you then use this repeatedly to compute $P^{\gcd(e_1, e_2)} \bmod N$?


Algorithm/encryption technique which outputs a set number of numerical digits e.g. 20 digits from a given input

Your question is not clear. Any deterministic compression functions an answer to your question.

$$C:\{0,1\}^* \to \{0,1\}^\ell$$ where $\ell$ is the output range, (20 numerical digits in your case and this may require some conversion from bits to digits).

A simple one is zipping with trimming. Zip the trim to 20 numerical digits.

However, in Cryptography we want the compression functions as one-way compression functions.

You may also be asking, the Cryptographic hash functions which are also one-way compression functions with pre-image resistance, secondary pre-image resistance, and collision resistance are required.

\begin{alignat*}{2}
  H:\{0,1\}^*&\longrightarrow& \{0,1\}^\ell \\
  \mathbf{m}&\longmapsto& H(\mathbf{m})
\end{alignat*} where $\ell$ is the output range. The definitions of resistances are;

Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=H(m)$. Consider storing the hashes of passwords on the server. Eg. an attacker will try to find a valid password to your account.
Second Pre-image resistant: given a message $m_1$ is should be computationally infeasible to find another message $m_2$ such that $m_1 \neq m_2$ and $H(m_1)=H(m_2)$. If possibe this can lead producing a forgery of a given message.
Collision resistance : if it is  computationally infeasible to find two inputs $a$ and $b$ such that $H(a)= H(b)$ with $a \neq b.$

The generic attacks on hash functions have the following complexities:

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

Your case, however, is a 20 numerical digits output, this is not secure since, 20 numerical digits has $\approx 67$ bits. In today standards, this is considered as trivially broken (computationally) since a collision attack with generic birthday attack on hash functions with $2^{67}$ output is $\sqrt{2^{67}} =  2^{33} \sqrt{2}$ with 50% probability. In, today's computing power, SHA-1 with 160-bit output is not considered secure for cryptography and removed from the standard.

You should use, at least, a secure hash function with around 256-bit output size like SHA-224, SHA-256, SHA-512 or SHA-3 series. You should not trim the output that falls into the computational feasibility of the attacks.


Is it possible to verify and relay an encryption key with a trusted but transparent third party?

I'm not sure what you mean by transparent.
With a trusted third party what you ask is trivial. But with etherium I believe you can't, the key would become public there is nothing secret on the blockchain.

If we wanted our own distributed third party this can be done. You can perform secret sharing and send part of the key to each member of the distributed escrow. They can then perform shared computing to verify the secret without revealing the secret.


The dth root unity in the Pollard Rho Algorithm

1) Because $r$ is a primitive root, there exists a $k$ such that $r^k = q$, so $r^{dk} = q^d$.

2) The sample code (lifted from section 3.6.3 of the Handbook of Applied Cryptography http://cacr.uwaterloo.ca/hac/about/chap3.pdf) assumes that the group has prime order. Pollard doesn't make this assumption.


Does signing multiple messages with the same RSA key weaken the encryption?

I'll ignore the term "encryption" in the title, since it is improper: signature is not encryption. Instead I'll try to answer the question:

  Does direct textbook RSA signing of hashes of 1000 messages $M_j$ per the textbook RSA signaing function $\mathcal S$, as $S_j=\mathcal S(H(M_j))=H(M_j)^d\bmod N$, weaken the resistance against signature forgery for other messages under the same scheme, given $(N,e)$ a public key with 1024-bit RSA modulus.

Yes, for too narrow a hash $H$. One attack strategy could be that of Yvo Desmedt and Andrew M. Odlyzko: A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, in proceedings of Crypto 1985.

The basic attack

Factors the $H(M_j)$ and keeps those that are $B$-smooth, forming a (sparse) matrix $A$ with one column per such $j$, one line for each prime $p_i$ that appears in such factorizations, collectively forming the factor base. The multiplicity of prime $p_i$ in $H(M_j)$ is at line $i$ column $j$ of $A$.
Factors many $H(M'_k)$, and for those which factors all are among the factor base, form the vector $V$ of the multiplicities of that $H(M'_k)$, and try to solve for $X$ the system $V=A\cdot X$ where $X$ is a vector with one entry per column in $A$, and operations are in $\Bbb Z_e$.
Once such $M'_k$ is found, computes the signature of $M'_k$ using

the multiplicative property: $\mathcal S(H\cdot H'\bmod N)=\mathcal S(H)\cdot\mathcal S(H')\bmod N$,
the known signatures $S_j$,
the coefficients in $X$, corresponding to powers of the $S_j$,
the fact that forall $p_i$, it holds $\mathcal S({p_i}^e\bmod N)=p_i\bmod N$.

It can work, or not, depending on:

The width of the hash. The narrower, the more smooths, the easier the attack.
The value of $e$. Lower $e$ (e.g. $e=3$) make the attack easier.
If the adversaries are able to choose some of the $M_i$; this allows the adversaries to try much more than 1000 messages in step 1, somewhat offsetting the effect of a wider hash.

In an improvement extending the applicability to less signed messages or wider hashes, pairs of $H(M_j)$ having a single prime factor larger than $B$ are kept separately if another $H(M_{j'})$ is in this case and shares the same larger prime factor, with the difference modulo $e$ in the respective multiplicities of the primes in the factor base for $H(M_j)$ and $H(M_{j'})$ used for an additional column in $A$. A further improvement uses two large primes.

It can be predicted about how many messages are required for a given hash width and $e$, and the work necessary. I wish I knew exactly how! There is an analysis in appendix C of the full version of Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann's Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures, in proceedings of Crypto 2009, but it does not account for $e$, nor of the large prime(s) improvement, nor of working under the constraint of relatively few non-chosen signed messages.

  would a padding scheme protect against it?

Yes, by making the input of the textbook RSA signature function $\mathcal S$ too large to allow the attack.


I'm getting a non-integer (float) private key in Paillier encryption

Looks like you missed the note on wikipedia:

  Note that the notation ${\frac {a}{b}}$ does not denote the modular multiplication of $a$ times the modular multiplicative inverse of $b$ but rather the quotient of $a$ divided by $b$, i.e., the largest integer value $v\geq 0$ to satisfy the relation $a\geq vb$.

As a side note, to make key generation even simpler, there is another note on wikipedia you may be interested in:

  If using $p,q$ of equivalent length, a simpler variant of the above key generation steps would be to set $g=n+1,\lambda =\varphi (n)$, and $\mu =\varphi (n)^{{-1}}{\bmod  n}$, where $\varphi (n)=(p-1)(q-1)$.


Is it possible to track down copies of WW2-era codebooks?

Yes, a good bunch of Japanese naval codebooks and related documents from WWII are available.

You might want to contact the National Archives and Records Administration (NARA) for that, as they hold the related NSA documents which have been declassified.

The “Declassified Documents Released to NARA” list at the NSA website points (among other things) to ample Japanese naval codebooks (random example: “NR 4037, ZEMA150, 45441A, 19440218, CODES AND CIPHERS: JAPAN JN-155 CODEBOOK”) as well as dozens of similar documents containing Japanese naval codebooks, naval call-signs, naval communications indicators, brevity codes, etc.

Looking at The Freedom of Information Act, it shouldn’t pose a big problem to get a copy of those documents to satisfy your academic curiosity.


References about a boolean function involving hamming weight

It is the hidden weighted bit function. There is more than one paper related to cryptographic applications of this function, but the full definition may be found, for example, in Chapter 3 of this paper:
Cryptographic properties of the hidden weighted bit function


Simulator in semi-honest model in real/model paradigm

It depends on the scenario. My intuition says that typically it would be used. In particular, the transcript that is generated during simulation includes the randomness of the corrupted party/parties and their incoming messages. Given this, it is possible to compute the outgoing messages sent by the corrupted parties. Since these messages must somehow embed the corrupted parties' inputs in a real execution, they would need to also be embedded in the IDEAL simulated messages.

Having said the above, note that it may be implicit. For example, in the EGL oblivious transfer protocol (see for example, Section 2.1 of this paper by Iftach Haitner), the receiver sends a message to the sender, and the sender replies. If the sender is corrupted, then the simulator only needs to generate the first message, and the second message which embeds the corrupted party's input is implicit (generated from the incoming message, input and randomness). As such, the simulator itself never needs to relate to the message.


How to generate two different keys out of a single password?

My problem with doing that is that if I use Scrypt for both, auth and key derivation, I could be exposing the key to the server (during authentication).

If you use two hashes then one failing breaks whole system. Using one reduces chance of being broken than using two.

  I'm pretty sure that to hash the password for authentication purposes I want to use Scrypt.

Scrypt isn't a hash, it is PBKDF. PBKDF2 is also a PBKDF, not a hash.

  How should I resolve that problem other than by using two different algorithms?

First of all, don't use two different PBKDFs. Then you have two different attack vectors, and you spend less time per PBKDF than with one strong PBKDF.

You should derive master key first, using some PBKDF (I would recommend Argon2, making sure strong settings are used and using salt). After master key is derived you should use KDF (Key Derivation Function) to do exactly what you ask for: Make two keys from one. Then you have K1 and K2. K1 can be used for encryption and K2 can be sent to server which also should hash it(PBKDF is useless there).

You should also consider if server should store salt (+you can access your data after HDD fail; -Server can try to break your password).


How secure is this cipher?

At first glance, not very.  It would appear to be vulnerable to a ciphertext-only attack, for example, the attacker can recover the plaintext given a ciphertext of about 10k (actually, he probably can deal with less), even assuming that all the attacker initially knows is that the plaintext is "ASCII English", and he has no initial knowledge of the $(\sigma_1, \sigma_2, ..., \sigma_n)$ permutations.

Since you're learning, I won't spell out the details.  Here is how I started with:

"ASCII English" is approximately 20% spaces; that is, 20% of the plaintext is the exact same byte value.
Within a single generation (where "generation" means "within 255 consecutive times we shift only $\sigma_1$), $\sigma_2(\sigma_3(...\sigma_n(P))...)$ will be a fixed permutation; hence the result of that will be the same value 20% of the time.

How can we use that to attempt to reconstruct $\sigma_1$ (up to a circular shift)?  How can we correlate data from different generations (hint: it's easier if we just assume that the $\sigma_2(\sigma_3(...\sigma_n(P))...)$ permutations from different generations are independent)?  Once we've reconstructed $\sigma_1$, how can we immediately recover the plaintext?


The usage of subkeys separates the collection of trust signatures from the key's usage. Trust signatures for the Web of Trust are created for you master key. This trust is inherited by your subkeys which are the ones used in the actual cryptographic operations (signing/decrypting). This has a few advantages:

Key rollover: You can use short lived subkeys (usually 1 year) which can be updated regularily without you losing the trust signatures collected.
Key compromise: As you stated, the master key should be stored offline to mitigate the consequences of a key compromise. If your subkeys are compromised, they can easily be revoked and replaced. Past communications will be left vulnerable but not future ones.


Encrypting cryptocurrency seeds for cold storage

Unless otherwise noted, I assume adversaries know the genuine QR-code, and can alter it and submit it for decryption. I posit the design requirements are:

Confidentiality of $\text{seed}$, to as high a level as the passphrase + key stretching of Argon2 allows.
Integrity of $\text{seed}$, to 64-bit security level [ample in the context, where we want to catch an incorrect passphrase, or an altered QR-code which decryption is attempted in a legitimate context, with some low limit on how many times].
Ability to encode an arbitrary $\text{seed}$ [e.g. because it was generated independently of the procedure; this also is necessary to allow a change of passphrase without changing $\text{seed}$].

I suggest to get rid of AES-GCM, because we can do without it, and most portable implementations [not using AES instructions] use data-dependent memory accesses which can create side channels. Also, questions A/D/E disolve. Towards this:

At step 5, generate 64 bytes [that is set 64 for tagLength in the invocation of Argon2]. Split the output into first 32 bytes $K_0$, and last 32 bytes $K_1$.
For confidentiality, compute $C\gets K_0\oplus\text{seed}$ and encode it in the QR-code. On decryption, do $\text{seed}\gets K_0\oplus C$.
For integrity, use Argon2i [1 for hashType] with $C$ as salt, $K_1$ as password, 8 as tagLength, minimum workfactor [that is 1 for parallelism, 8 for memorySizeKB, 1 for iterations], other parameters as in step 5 [empty key, empty associated Data, same version]. The 8-byte result $T$ is encoded in the QR-code. On decryption, it's compared to decide is we accept the QR-code with the given passphrase. That comparison needs not be side-channel protected, but if it fails, nothing except an error indication must be output.

Security arguments:

The output of Argon2 is computationally indistinguishable from random, except if the passphrase is guessed; hence $C$ leaks nothing about $\text{seed}$.
The integrity test using $T$ is functionally a MAC keyed by an output of the main Argon2 of step 5; that's why the extra Argon2 can be fast.
We use Argon2i for integrity since it promises maximum side-channel resistance, and key stretching [which the other forms optimize] is not an objective.
Removal of AES makes testing a passphrase only marginally easier, because the computational burden of AES decryption is negligible compared to the main Argon2 of step 5. In the check of a $\text{seed}$ candidate the way that's done on normal decryption, the extra Argon2 is arguably comparable in cost to AES-GCM. And the cost of AES decryption is typically low compared to other possible tests of a $\text{seed}$ candidate (like testing it against a public key or signature).

On the $\text{salt}$ size (B/C), the main goals of $\text{salt}$ are

When adversaries attack many QR-codes and are content with breaking any [rather than one or few in particular],  $\text{salt}$ prevents the reduction (by a mere factor of two) in the expected work for dictionary attacks that would occur for QR-codes which $\text{salt}$ collide.
Making it futile to pre-compute Argon2 outputs [e.g. building rainbow tables] before getting one's hand on QR-code(s) [for a faster attack, or leveraging resources otherwise not available].

The proposed 12 bytes for $\text{salt}$ are fine from both standpoints: if we assume $2^{40}$ QR-codes, there's about one chance in $2^{12\cdot8-2\cdot40+1}$ (one in 130,000) that the first bullet applies. Except for passphrases and Argon2 parameters so weak that they give no useful protection, the second is no issue. In fact, from the perspective of one particular user, 6-byte $\text{salt}$ would be enough as long as the passphrase is not massively reused.

On using $\text{salt}$ as IV for AES (D): that's not an issue as long as there is no collision of both $\text{salt}$ and passphrase [because Argon2 makes no use of AES, hence the identity quickly dissipates]. If there is collision of both $\text{salt}$ and passphrase, both AES-GCM and this answer's proposal have the same issue: leak of $\text{seed}$ encoded in one QR-code leaks $\text{seed}$ in another. That's one area where AES-CBC has an advantage [because a difference in the first 16 bytes of $\text{seed}$ is likely to save the day].

GCM has message authentication. But I don’t see malleability as an attack vector.

AES-GCM encrypts just as AES-CTR does (except for an offset of one in the IV), but adds authentication. In the original proposal, GCM authentication has at least one important function: it catches using the wrong passphrase on decryption. Depending on what $\text{seed}$ is used for, malleability in the decryption could well be an attack vector. ECDSA is not claimed to resist in an attack context where adversaries can flit bits of the secret key.

Note: if the ability to encode an arbitrary $\text{seed}$ is not needed, we can set $\text{seed}\gets K_0$ and save the 32 bytes of $C$ [since it's all-zero]. This does not change security w.r.t. an adversary knowing the QR-code. If we want extra protection against adversaries not knowing the QR-code (which is quite reasonable), we can rename the $\text{salt}$ field of the QR-code to $\text{pepper}$ [to denote that it's secret to a degree], and increase it's size to say 24 bytes [which combined with the entropy in the passphrase and the Argon2 key stretching is more than overkill].


What's the actual difference between RSA encrypting and Descrypting and RSA Signing?

So I was wondering, is there any difference between "Encrypting + Decrypting" and "Signing + Verifying"?  I mean, if I hash the message and then encrypt it, wouldn't that be the same as Signing it?

First of all RSA or any public key is not preferred for encryption, we prefer a hybrid-cryptosystem where a key is transferred/exchanged with public-key cryptography and the message is encrypted with a symmetric encryption scheme with the transferred/exchanged key.

RSA encryption to be secure requires a padding scheme like PKCS#v1.5 or OAEP. The letter is preferable since there is a security proof. The modulus size prevents you from encrypting arbitrary sizes so you need to encrypt a message dividing part like in block ciphers then perform the slow encryption many times.

RSA signature with PSS requires hashing not only for the security but for the message size. There is also RSA Full Domain Hash (FDH) Signature that hashes and signs and it has existentially unforgeable under adaptive chosen-message attacks.

If you hash a message then encrypt, then except you, nobody can verify the signature. You need to use your private key for signatures even for RSA-FDH. Keep in mind that it is not advisable to use a key for both encryption and signatures.

So the main difference in encryption vs signature is the used key and padding requirements. If you encrypt a message without padding you will have many attacks like it is malleable and see more here Twenty Years of Attacks on the RSA Cryptosystem

  But again, is this because of how those functions are made in this library? or because the "operation" and the output are done in different ways depending on if it is Signing or Encryption?

Yes, the operations are done differently since they require different padding to be secure.

  If they are different, then why do we need the Signing part?

Because they are different so one needs different functions. Even if they are the same one still needs these functions to remove the ambiguity. Think about there is only encrypt and decrypt functions and the developers need to tell everyone to use decryption for signature and encryption for verification. Some people will use the encryption for the signature that will reveal unwanted information. Unfortunately, this is due to the RSA that has both encryption and signature.

  Isn't encrypting with private and decrypting with public secure enough to "sign" it?

No, you need hash then sign for RSA-FDH and hash and apply PSS then sign.

signature = RSA-FDH(Hash(message))

of

signature = RSA-PSS(Hash(message))


How to construct encrypted functions (with either public or private data)?

Theoretically, with fully-homomorphic encryption (like with Gentry's scheme), you could make a circuit (with memory) which computes over encrypted data and outputs encrypted results. The circuit could be a general-purpose CPU, and the encrypted data the code which is to be executed (reading this again, I think this is what @ByteCoin suggests).

Since this method requires doing some pretty heavy stuff for every gate in the circuit (including every gate which is used for RAM in our custom CPU) and for every clock cycle as well, the cost would be tremendous (polynomial, yes, but with a hell of an exponent).

Now this would work over encrypted data, and produce encrypted results. If you want an encrypted function which runs over public input data and produces a public output, then the party who holds the decrypting key must be involved at some point. Without such a party, I don't think it is known whether it is doable.


PBKDF2 is not reversible using any semi-safe underlying hash function, including for instance SHA1 or even MD5.


Assuming your key mixing layer uses XOR:

$M \oplus K_0 \oplus K_1 \oplus ... K_r$
$K_0 \oplus K_1 \oplus ... K_r$ effectively compresses into one, single key
Equivalent to $M ^ K$ in terms of security

More importantly, since the only key addition layer is at the front, and the S-box and permutation layer are assumed to be publicly known, a single known plaintext attack could break the construction: Simply encrypt the known block of information and then invert the permutation and S-box layers on the ciphertext. This leaves us with $M \oplus K$, which, since we know $M$, means we can do $M \oplus M \oplus K$ and recover $K$. Granted, $K$ is only the XOR sum of $K_0 \oplus K_1 \oplus ... K_r$, but we don't actually need the values of $K_0, K_1, ... K_r$ individually. We only need their sum in order to perform the encryption/decryption operation.

It is important for there to be key addition layers before and after the application of a round function, if the round function is to provide security. They do not have to be immediately prior to or after each application, i.e. adding a key, iterating the core permutation a bunch of times, then adding a key again is a valid strategy as well.


The role of the dealer in visual cryptography

The dealer is one of n participants or it should be from outside?

The dealer, knows the secret as he's the one who shared it. Thereby it makes no sense to give him a share as well, unless you have a such a scheme that requires all partys to collaborate to recover the image, but then the question becomes: "Why bother secret sharing at all if the dealer could just store it if consensus with him is required?"

TL;DR: He can be part of the participants, but there's no benefit of him being one.


How obvious is it to decrypt numerics encrypted with a reused one time pad?

Yes, the same weaknesses apply. Text on computers is a bunch of numbers; a OTP encrypts a sequence of numbers modulo 2.


There are few requirements for the additional data in the GCM document of NIST.

There are some limitations on the size of the AAD, the maximum is $len(A) ≤ 2^{64}-1$ in bits.

Furthermore the following recommendations about the size apply for 128 bit tags:

  Therefore, the total number of blocks of plaintext and AAD that are protected by invocations of the authenticated encryption function during the lifetime of the key should be limited. A reasonable limit for most applications would be $2^{64}$, consistent with the requirement on the number of invocations in Sec. 8.3.

and for shorter authentication tags Appendix C applies further restrictions on the length of ciphertext (or equivalently plaintext) and AAD combined.

Those are all the restrictions that apply according to the NIST document.

I'll however add another restriction: AAD is defined in bytes. Whatever you do, for a successful authentication, the AAD must be encoded to the same bytes. That is: the encoding of the AAD must be a canonical encoding. Obviously if you encode a sequence number in little endian and later in big endian then you're in trouble. Same thing if it is unclear where one field ends and the other starts.

  Is there any "classic" used information worthwhile to be used? Can for example a username or the name and surname of a person be suitable to encrypt a message with AES GCM?

NIST again offers a few options:

  The controlling system or protocol may protect against such an event by monitoring for any duplication of the IVs that are presented for authenticated decryption. Alternatively, certain identifying information can be incorporated into the AAD. Examples of such information include a sequential message number or a timestamp.

I'd say it's a good idea to include as much identifying data in your AAD as possible. Note that you do not have to send the AAD data as long as you can produce it at the sender and the receiver. At least you should be able to prevent replay attacks and to distinguish between sender and receiver. If you cannot do this using the key/IV combination then you'd have to use the AAD (or plaintext) for that.

So yes, name and surname are a good idea as they identify the sender. Beware that names are however often not unique (hence UUID's etc.), something you'd sorely want in an identification scheme.

One thing you do not have to include is the IV, the IV is authenticated by default. And in case you're a greenhorn in cryptography, including the key is a bad idea as well.


1a lHash: What is this and where does this come from?

That's in PKCS#1 v2.1: RSAES-OAEP-ENCRYPT ((n, e), M, L):

  2a. If the label L is not provided, let L be the empty string. Let
           lHash = Hash(L), an octet string of length hLen (see the note
           below).

1b) PS: A string of zeros, but how much zeros?

Similarly for this question, lets look at the actual standard:

  2b. Generate an octet string PS consisting of k - mLen - 2hLen - 2
           zero octets.  The length of PS may be zero.

2) We have a seed which , is some random number. We put this seed into a MGF, a Mask Generating Function, and XOR the outcome with the MB. This is our maskedDB. Correct?

Well, yes, but you XOR with DB, not with MB (whatever that is). It's in steps 2c..2f of the linked section of PKCS#1.

3) We put the maskedDB to the MGF again and XOR it with the seed. This is our maskedSeed.

4) For the final EM (encrypted message) we prepend some zeros. What do we do with EM then?

You continue with steps 3a..c and of course step 4 of the standard, which basically means:

3a) creating an integer from the octet string you've just constructed
3b) modular exponentiation with the public exponent and modulus of the public key (also known as raw or textbook RSA)
3c) creating an octet string from the result again

And 4, output the result (well...duh).


How does this attack alter the runtime analysis for brute forcing hash collisions?

Absolutely nothing whatsoever.

The traditional brute force analysis counts the total number of hash computations required, and nothing else.  In this model, the best we can do is hash $O(2^{n/2})$ distinct messages, and then scan them all, and see if there are two messages that hash to a common value.

If the hash function acts like a random function, we can't do any better; however if we look at actually implementing this attack, we notice that this attack also requires $O(2^{n/2})$ space, and that's actually a bigger problem than the computation required.

What rho (and parallel rho) collision attacks do is increase the number of hash computations required by a constant factor (nothing huge, but greater than 1); and also drastically reduce the amount of memory involved.

If we're actually looking to do a brute force collision (say, of a 100 bit hash function), a rho collision attack would be much more feasible than anything requiring you to store $2^{50}$ or so hashes.  However, if you're just thinking about how much processing power it would take, the traditional birthday attack scores better.

And, because a standard birthday attack against a 256 bit hash function would require $O(2^{128})$ hash evaluations, which we believe is infeasible, a rho attack would require even more (and hence, also be infeasible).

If you're worried about the parallel side of it, well, the possibility of parallel computation is already baked into the analysis; it is commonly believed that $O(2^{128})$ (or more) hash evaluations is infeasible, even if someone had vast (but realistic) quantities of parallel processors.

BTW: DJB's point wasn't that parallel rho attacks are actually a threat against SHA-256 or SHA3-256; he is trying to show that attack is better than a quantum computer running Grover's algorithm to search for collisions (and so if those hash functions are safe against a parallel rho attack, they are certainly safe against a quantum attack).


order of elliptic curve divisible by prime

You want to work in a large subgroup of prime order because you want that for the ECDLP in the subgroup you are working in the generic bounds for solving the ECDLP (only square root attacks) apply and thus the security parameter can be chosen accordingly.

If you would work in the entire group the ECDLP is attackable by algorithms such as Pohlig-Hellman, Pollards' $\rho$ method or the babystep-giantstep algorithm. Additionally one avoids curves (such as supersingular ones) that are susceptible to the MOV and SSSA attack (such that you can even use subexponential algorithms).


How can Hashed Value be same in length extension attack?

It is not about having the same hash value. It was about forging a message.
It was first executed on Flicker API where the signature was;
$$tag = \operatorname{MD5}(\text{secret_key}\mathbin\|\text{known_data}),$$ the $tag$ and $\text{known_data}$ send to server, and the server can verify it with the $\text{secret_key}$.
The attacker can extend this message this into
$$tag_2 = \operatorname{MD5}(\text{secret_key}\mathbin\|\text{known_data}\mathbin\| \text{pad1}\mathbin\|
 \text{appended_data})$$
Now you can send the server $tag_2$ and extended message $$\text{known_data}\mathbin\| \text{pad1}\mathbin\|
 \text{appended_data}$$
The server will accept it since it was assumed that the key used in the signature will protect against the forgeries, but not. It was known way before the attack.
It can similarly be applied to SHA-1 if it is used as $$tag_x = \operatorname{SHA-1}(\text{secret_key}\mathbin\|\text{known_data})$$
or any hash function that has no resistance to length extension attacks.
To mitigate one either need HMAC or KMAC of SHA3.
If you ask about finding collisions, it is possible in theory, but not in practice.


Are there any valid, and person readable, checksums possible?

You could use a concept similar to the PGP Word List, which attempts to make a binary-representative equivalent of the NATO Phonetic Alphabet, so that fingerprints (bytes) can be expressed vocally in a relatively unambiguous way.

Of course, using per-byte words in the case of MD5 means you need 16 words to produce a readable checksum, which may be potentially excessive for your purposes. If this is the case, your options are to either truncate the hash (which is potentially not ideal from a security perspective) or to invent additional words codepoints to shorten the total string length. Unfortunately the required dictionary size raises geometrically ($2^n$) whereas the length only reduces linearly, which means you need much larger dictionaries to get slightly shorter strings. You'll have to work out a balance point.


Cryptographic Challenge: How to Say Something Confidentially to Snowden?

Generate a file of cryptographically strong random data at least as long as the message to be sent.  This will allow communicating the secret using the random data as a one-time-pad. I.e., produce the ciphertext by using a bit-by-bit combining function such as XOR.
Purchase a plane ticket for an international flight connecting through Sheremetyevo airport.
Burn a copy of the OTP data onto a CD-ROM. Label it "Lady Gaga" and lock it in a briefcase handcuffed to yourself.
Take the flight. During your layover, locate Snowden in the international travel area.
Whisper the secret to Snowden.
Both of you then giggle loudly something about Lady Gaga.
Drop the CD-ROM in the trash so the spooks don't have to report home empty-handed.
(Optional) exchange public keys with Snowden to secure your future communications.

EDIT: OK, I felt bad about leaving a response that might be interpreted as just trolling. But in all seriousness, this is a classic identity bootstrapping problem.

Once we have identity authentication worked out, message integrity and confidentiality are basically solved by standard encryption systems. There's no magic bullet for bootstrapping identity, but here are the questions I ask myself when trying to approach the problem:

First: Precisely what facts are being authenticated?

For example, do you have a public key which claims to be Snowden's and you're trying to prove that it is genuine? Authentication has a cost, why would he go out of his way to prove that to you?

An easier problem to solve may be "If Snowden wanted to receive a message from me how could he do so securely?"

Second: To whom are these facts being authenticated?

Are you trying to prove to Snowden that a message you sent is genuinely from you? Or is some unknown party claiming to be Snowden expected to prove to you that a message you received is from the authentic Snowden?

Third: Who has what to lose from a successful attack?

Perhaps you are sending something to Snowden and then relying on him to do a perfect job of authenticating what he receives (i.e., proving the absence of an active man-in-the-middle attacker). But if he doesn't care at least as much as you do about the security of the message, he might do a halfhearted job of it you might continue on transmitting messages insecurely.

Fourth: How far do these credentials extend?

In other words, will your actions allow Snowden to do more than just verify you? For example, would he be able to impersonate you to a 3rd party? How about the other way around?

In summary:

A cipher is a device for converting a plaintext confidentiality problem into a key distribution problem.

An ephemeral key agreement algorithm is a device for converting a key distribution problem into an authentication problem.

A signature algorithm is a device for converting a message authentication problem into an identity problem.

If you can somehow establish trust for authentication credentials in one or both directions, the rest is mostly a solved problem. But this can only be built on top of human systems: What will it take for you and/or Snowden to believe that the other party is authentic?


Hill Cipher - Unknown plaintext attack, known key

You don't. You just decrypt it. I can't think of a language that uses more than 36 letters apart from the Chinese family but then again I'm not a linguist.

Decrypt to a reasonable $n$ and then use the character frequencies to infer the language (and hence the modulo). Some trial and error may be required untill you get it right but for values of $n$ less than $2^{32}$ it shouldn't give you any practical problems on a desktop computer.


Feldman's VSSS: Showing the Correctness of shares that are Consistent

There is no such thing as an incorrect secret. There is just some secret, that must be uniquely defined by the distribution phase.


what is meaning of operator " := " in cryptography?

Lindell and Katz, in their book Introduction to Modern Cryptography, use;

$\leftarrow$ as possibly probabilistic process assignment.
Some others use $\stackrel{r}{\gets}$, $\stackrel{\\\$}{\gets}$, $\gets_{R}$, and $\gets_{\\\$} $
Actually, the $\gets_{\\\$}$ fairly common.

$:=$ for the deterministic process assignment.
In some context, the $\leftarrow$ can be the same as Lindell and Katz 's $:=$. This former is more common. In some contexts, it is $=$

$=$ for equality

$\stackrel{def}{=}$ for defining a variable.

More on $\leftarrow$ and variants

When $X$ is a value, the $x \leftarrow X$ is used for  deterministic assignment, and

When $X$ is a probability distribution, the $x \leftarrow X$ is used for sampling.

When $X$ is a set, the  $x \leftarrow_R X$  is used to denote sampling from the uniform distribution over the set $X$.

Note:

In reading books, one needs to check the existence of the notation page(s) or the notation section. Many good books have a section like L&K's Index of Common Notation section (page #533 in the second edition).
In the articles, the authors usually define them where they first occur, therefore, look for the first occurrence of the symbol.


Operation which needs much computing power to be created, but just a little to be solved?

Lots of problems are hard to solve but easy to check. For example:

finding hash pre-images of particular values such as 0
calculating discrete logs of small numbers modulo a prime
finding the factors of a large composite of a special form like $2^p-1$

I don't think there's an essential difference between solving and checking they're just arbitrary descriptions of the operations.

I imagine an unstated requirement of your question is that it should not be possible to pretend to have solved hard problems by generating random solutions and then saying that you arrived at the solution by solving the hard reverse problem.
This is a bit like shooting arrows randomly into a wood and then painting targets round the arrows wherever they have stuck in the trees.


How to figure out DES mode used given plaintext and ciphertext?

Let's assume that we're talking about the following classic modes for block ciphers (although there are certainly more): ECB, CBC, CFB, OFB and CTR.

First of all the second message is way too long to fit into the ciphertext, so we can safely discard that possibility.

Then we can look at the size of the plaintext and ciphertext. The plaintext message is 14 character, which are generally encoded to 14 bytes. The size of the three ciphertext are 14, 16 and 14 bytes.

Now ECB and CBC are generally using padding, so that the padded plaintext and the ciphertext are Y times the block size. The other modes are streaming modes so they don't require padding, and the size of the messages are identical to the plaintext size.

So with that in mind, ciphertext one is using streaming (CFB, OFB or CTR), ciphertext two is using ECB or CBC and ciphertext 3 is using streaming again.

Can we find out more? Sure, message 1 and 3 are clearly starting with the same ciphertext.  Now for CTR only the first half of the IV was used, so it is less likely that will correspond with either of the two ciphertext. That would only be the case if the second half of the IV was set to all zeros (the initial counter value is identical to the IV) for the other modes.

That leaves CFB and OFB, and if we look at those schemes we see that the calculation of the first ciphertext is exactly identical to each other. Only after that there are differences, because one uses ciphertext feedback, while the other uses output feedback.

Can we say much more? I don't think so. We lack any information to distinguish ECB from CBC or CFB from OFB (other than knowing that if one ciphertext uses one, the other one must have been generated using the other).

If there are ways of using the blocks of one cipher to determine the precise mode of another then I don't see it. OFB and CFB start with encrypting the IV, and CTR and CBC don't do that.

Once the calculations end up with a different input to the block cipher and are permuted, we cannot learn anything from them unless we know the permutation - i.e. the key. We can just tell the blocks apart.


What "Tag Length" should be used for the EAX MAC?

While the EAX mode permits truncating the tag to any length $\tau$ between 0 and $n$ bits, where $n$ is the block size of the underlying block cipher, this should only be taken as a statement that truncating the tag in EAX mode does not introduce any security issues beyond the obvious (an attacker only needs $2^\tau$ attempts to froge a $\tau$-bit tag by brute force).  Still, in the absence of a particular space or bandwidth constraint that would require a shorter tag, I see no reason not to use a full-length tag ($\tau = n$).

(I suspect the main reason for introducing a variable tag length into EAX was because CCM had one; see the table in figure 4 of the EAX paper you cited.  EAX was designed as a replacement for CCM, and so one of the main design goals was to be able to do anything CCM did, only better.  If EAX had been specified with a fixed tag length, someone might have cited that "missing feature" as a reason to use CCM over EAX.)


So, there are a few things here.

  8 in the first case and 18 in the second

Yes, that's correct but only if there is enough sample data.  These last two tests need looads of numbers. In fact, in excess of the recommended minimum 10 x 1 million bits.  I don't know exactly, and NIST doesn't say exactly.  If happy, the test will return something like the bottom of the print out in  Interpretation of the results of NIST (p)NRG suite, innocently plagiarised below:-

  4  12   3  15  10   4   7   6   3   7  0.011440     70/71      RandomExcursions
  6   8   6   7   8   6   7  11   7   5  0.937294     70/71      RandomExcursions
  6   6   4   4   5  12   9   9   8   8  0.491599     71/71      RandomExcursions
  2   6   2  10   9  11   9   5   7  10  0.127498     71/71      RandomExcursions
  5   7   5   8   9   8   9   4   7   9  0.881013     71/71      RandomExcursions
  6   8   4   8  12   8   3   8   8   6  0.519816     69/71      RandomExcursions
  5   5   7   5   3   7  10   7   9  13  0.275709     70/71      RandomExcursions
  3   6  11   6  14   6   6   3   8   8  0.099089     71/71      RandomExcursions
  7  13   8   4   6   4   5   8  10   6  0.339044     71/71      RandomExcursionsVariant
 11   9   6   6   8   7   7   1   6  10  0.362174     71/71      RandomExcursionsVariant
 10   8   9   8   8   6   8   3   6   5  0.781926     70/71      RandomExcursionsVariant
  9   8   7   8   5  10   9   6   6   3  0.754127     71/71      RandomExcursionsVariant
  9  10   7   9   5   5   7   9   5   5  0.808725     70/71      RandomExcursionsVariant
  5  14   8   5   2   3  11  11   6   6  0.025193     70/71      RandomExcursionsVariant
  9   3   6   5  10   8   7   7   8   8  0.808725     70/71      RandomExcursionsVariant
  6   5   5   8  10   8   7   9   5   8  0.901761     69/71      RandomExcursionsVariant
  3   9   5  12   6   6   6  10   8   6  0.437274     71/71      RandomExcursionsVariant
  3   6   7   2  10  11   6  10   7   9  0.238562     71/71      RandomExcursionsVariant
  4  10   6  12   3  13   4   4   5  10  0.033552     71/71      RandomExcursionsVariant
  7   2  15   7   7   9   7   4   8   5  0.083381     71/71      RandomExcursionsVariant
  8   6  13   6   6   6   5   9   7   5  0.577844     71/71      RandomExcursionsVariant
  6  15   6   8   6   5   8   4   3  10  0.083381     71/71      RandomExcursionsVariant
 11   4   7  10   6  10   3   8   6   6  0.437274     71/71      RandomExcursionsVariant
 11   5   4  11   5   9  10   4   7   5  0.295803     69/71      RandomExcursionsVariant
 10   5   8   6   4  13   4   7   8   6  0.339044     70/71      RandomExcursionsVariant
 10   5   6   7   5  11   8   8   7   4  0.696376     71/71      RandomExcursionsVariant

  obviously redundant due to correlations

They're not correlated, unless your data is :-)  The suite takes your sample set and partitions it into multiple streams/chunks. Each test is run on a different sequence.  That's why you need so much data.  I typically use at least 10 times the 10 x 1 million bits (~10MB). Even more is even betterer.

  what if only one of them is not passed, what should that mean?

That your sample is properly random.  Or to be mathematically and philosophically pedantic, there is insufficient evidence to suggest that your sample set is not independently and identically distributed.  Again from that example:-

The minimum pass rate for each statistical test with the exception of the
random excursion (variant) test is approximately = 96 for a
sample size = 100 binary sequences.

The minimum pass rate for the random excursion (variant) test
is approximately = 67 for a sample size = 71 binary sequences.

Because randomness is quite pesky, there is no theoretical threshold that can be used as a hard cut off in the (is random?) decision process.  And the issue is confounded by multiple independent tests that might contradict each other on the same data set.

From experience, you tend to look at the results and see what sort of feeling you get.  A very few test failures probably do not mean anything adverse.  Rerunning the tests on another sample set might produce slightly different results.  Experience is required.  When your RNG is misbehaving, it will be pretty obvious with multiple p values near 0.0 or 1.0.  NIST use a 1% decision rule, but a bad RNG will be way outside that.