How would using only one s-box affect security of Blowfish?

Because I didn't get any answer, I did some experments with Blowfish's F function and here are my observations:

Because Blowfish's F function is not bijective, on average only every second value is returned and therefore different input can output same value (F(x) = F(y)). By reducing number of S-boxes this non-bijectivity becomes even worse. About 8 to 32 of inputs will result in F(x) = 0. But problem is worse, because addition hides problem; With F() with XORs instead of additions about 2^18 inputs will output 0. This happens, because (S(X) xor S(X) xor S(X) xor S(X)) or (S(X) xor S(X) xor S(Y) xor S(Y)) ... is always 0. So addition breaks symmetries a bit.

I have also found comment by David Wagner on question about strength of Blowfish with broken F (((S_1[a] + S_1[a]) ^ S_1[a]) + S_1[a]). He overlooked that also the same input byte is used. So he was answering my question.

  For what it's worth (which is not very much), I don't immediately see
  any plausible way to exploit this on the full Blowfish, though I
  haven't spent any serious amount of time thinking about this.  16
  rounds, with key-dependent S-boxes, forgives many sins.

https://groups.google.com/forum/#!topic/sci.crypt/21SwIdSqOo8

Considering the S-box is unknown, addition and 16 rounds I think it should be fine, but I don't think it's a good idea.


SSL - encrypt with private key and then with public key?

You cannot "encrypt" with a private key.

Encryption provides confidentiality of the encrypted message.

If the public key performs decryption, and the public key is public, then anyone can decrypt the message. So "encrypt with the private key" is not possible.

This notion may be popular, but it is incorrect.

It stems from the fact that signing a message with textbook RSA is equivalent to public key encryption done in reverse. However, there are many problems with this:

Textbook RSA does not provide a secure signature/encryption scheme, and is not used
Padding and hashing ensure that the signature process is in fact not the same as the encryption process done in reverse.
Few, if any, other algorithms even operate in a similar manner. E.g. there exist signature schemes that you cannot encrypt with, and therefore signatures being "encrypting with the private key" is not even a vaguely correct analogy.

So your questions can be translated to something more accurate:

  When establishing a connection in the SSL protocol, does the protocol always require that the message is first signed using side A's private key (so side B knows that only A could have signed it) and then is encrypted with B's public key so that only B could decrypt it?

When establishing a connection, it is assumed that A's public key is already signed by a certificate authority (that has vetted A's identity). First the certificate and public key are presented to B. B has the public verification key of the certificate authority pre-installed, and can use it to verify the signature on the certificate and public key. There is a nice outline of the process on our information security sister site.

  In what case would side A encrypt the message only with B's public key and then just send it?

Situations where the message is not signed include:

Broken protocols vulnerable to man-in-the-middle attacks
When A and B already share public keys with each other

The initial key exchange could use signatures, but the actual messages sent back and forth may only use MACs rather than signatures.

When A desires deniability about having sent the message to B


Hash function that allows to decide if A > B if you only have hash(A) and hash(B)?

For hash function $h : \{0,1\}^* \rightarrow \{0,1\}^k$, this is not possible. This is because there are more possible inputs than outputs (pigeon hole principle). And this means that for some $A < B$ we have $h(A) = h(B)$. Thus there will be no way to tell the order of $A$ and $B$.

Addition:  To address some of the comments; note that this answer only talks about hash functions defined as functions where the domain is the set of all bit strings and the codomain a set of bit strings of some fixed length $k$. It also assumes that inputs $A$ and $B$ are interpreted as integers (as specified in the question).

The argument only uses that such a hash function must have collisions. We can in fact generalize the argument to any hash function with collisions (i.e., also functions with different domain and codomains). Note that the argument only assumes the existence of collisions and thus holds even if the hash function is collision resistant.

The argument says that for such hash functions there will be some pairs of inputs, those defining a hash function collision, where the order cannot be decided from the hash alone. What happens on other inputs pairs the argument does not directly say anything about.

It is true however, as some comments point out, that if we define hash functions to include functions completely without collisions, then the argument does not hold for all hash functions. However, for functions where my argument does not apply we can use the argument of fgrieu, to show that a hash function with the desired properties can at least not be pre-image resistant.


Understanding double hash and 0 block prepending to mitigate length extension attacks

The objective of the construction $H'(m)=H(H(0^b\mathbin\|m))$ is not to strengthen $H$ against collision attacks; as noted in the question, that does not work.

The objective is preventing a length-extension attack. In such attack, an adversary knows the hash $h=H(m_0)$ of some unknown $m_0$, and the length $l$ of $m_0$. Then from $h$ and $l$ s/he constructs a short $m_1$ such that for any given $m_2$, it is easy to compute $h'=H(m_0\mathbin\|m_1\mathbin\|m_2)$. Essentially, $m_1$ is the padding internally appended to $m_0$ in the normal computation of $h=H(m_0)$, so that the internal state of the hash after hashing $m_0\mathbin\|m_1$ is the known $h$.

A length-extension attack can matter in practice, e.g. $F_k(m)=H(k\mathbin \|m)$ is insecure as a Message Authentication Code if $H$ has a length-extension property, as SHA-1, SHA-256 and SHA-512 do. That's one reason to use HMAC to build a MAC or Key Derivation Function.

If the $0^b$ is the question's construction was absent, as in $H'(m)=H(H(m))$, we'd have the property: $\forall m,H'(H(m))=H(H'(m))$. We can construct some (largely artificial) protocols which would be secure for $H$, but are insecure for $H'$ due to that property; and correspondingly, that property makes some security proofs hairy, impossible, or weaker. With $H'(m)=H(H(0^b\mathbin\|m))$, that or similar properties do not hold, which is good for simpler/stronger security proofs.


Are SSH key-pairs an example of a zero knowledge proof?

At step 3-4), the server can use the protocol to decrypt any message encrypted with the public key of the client. The server is not able to decrypt alone because it does not know the secret key of the client, so the protocol is not perfectly zero-knowledge.
Moreover, the protocol is not a proof of knowledge because you cannot build an efficient knowledge extractor (see "validity"). At best, this protocol prove that the public key of the client is "well formed".


MD5 and SHA-1 have a lot in common; SHA-1 was clearly inspired on either MD5 or MD4, or both (SHA-1 is a patched version of SHA-0, which was published in 1993, while MD5 was described as a RFC in 1992).

The main structural differences are the following:

SHA-1 has a larger state: 160 bits vs 128 bits.
SHA-1 has more rounds: 80 vs 64.
SHA-1 rounds have an extra bit rotation and the mixing of state words is slightly different (mostly to account for the fifth word).
Bitwise combination functions and round constants are different.
Bit rotation counts in SHA-1 are the same for all rounds, while in MD5 each round has its own rotation count.
The message words are pre-processed in SHA-0 and SHA-1. In MD5, each round uses one of the 16 message words "as is"; in SHA-0, the 16 message words are expanded into 80 derived words with a sort of word-wise linear feedback shift register. SHA-1 furthermore adds a bit rotation to these word derivation.

The extra bit rotation is what makes SHA-1 distinct from SHA-0; it also makes SHA-1 much stronger against collision attacks, and, indeed, SHA-0 collisions have been found (with effort $2^{39}$, thus highly doable) while SHA-1 collisions are much more difficult.

We don't have a true theory of what makes a hash function strong. However, we can still have some "gut feelings", and my own intestine tells me that in the case of MD-like functions (MD4, MD5, SHA-0, SHA-1, and the SHA-2 functions), the two important points are:

Rotating bits a lot. Collision attacks based on differential paths try to induce small differences and keep them from propagating non-linearly everywhere; a useful tool for that is the lack of carry beyond the upper bits in word-wise additions (a difference in the upper bit in one of the operands of an addition modulo $2^{32}$ propagates to the output with probability $1$; two such differences cancel each other reliably). The 1-bit rotation added in SHA-1 is effective at making differential paths harder to find.
Doing "enough work". If you count the number of elementary operations per input byte (which more or less translates to code size or speed, especially on GPU), you will see that SHA-1 is about 30% heavier than MD5, while SHA-256 is close to twice heavier than SHA-1. SHA-3 candidates were also, as a rule, "heavier" than SHA-1 (some could get faster by leveraging SIMD opcodes in CPU, but still had more operations per input byte).


Known vs. Chosen (plaintext and ciphertext) and RSA

I'm not exactly certain what answer you're looking for; I tried to cover all the obvious bases.

Actually, with RSA, we generally assume that the attacker knows the public key (the modulus $n$ and the public exponent $e$); with that, he can encrypt as much plaintext as he cares to (by selecting a value $M$ and computing $M^e \bmod n$). So, in that sense, the term 'known plain-text attack' doesn't apply, as we assume the attacker can do a chosen plain-text attack.

As for the variant "what if the attacker has some plaintext/ciphertext pairs, but doesn't have the public key; what can he do?  Actually, it turns out that if the public exponent isn't too large, the attacker is in luck; if the attacker takes two known plaintext/ciphertext pairs $P_1, C_1$ and $P_2, C_2$, he can compute $gcd( P_1^e - C_1, P_2^e - C_2)$ for plausible public exponents; if he guesses the correct one, that value will be $k\cdot n$ for some integer $k$ which is extremely likely to be small.  That gives him the public key.

As for guessing the decryption exponent, well, I suppose that the attacker could try, but he's not likely to have success.  It is known that knowledge of encryption and decryption exponents is equivalent to factoring; that is, if you know $e$ and $d$, you factor $n$ (and if you know how to factor $n$, you can compute $d$ given $e$). Hence, guessing the decryption exponent is hard; if it wasn't, the problem of factorization wouldn't be easier.  (And, if you're asking "why can't you step through all the possible possible private exponents", the answer is that $d$ is generally only a few bits smaller than $n$; if $n$ is 1024 bits, $d$ might be 1020 bits; that's rather too many possibilities to step through).

As for a literal "ciphertext-only attack", where an attacker is given some ciphertext without either the corresponding plaintext or the public key, well, on the face of it, that looks to be difficult; however we generally don't assume that attackers are hobbled in such extreme ways.


Can $y^2=x^3-x+1$ elliptic curve with $GF(3^m)$ where $m=97$ be used for Diffie Hellman key exchange?

This curve is thoroughly insecure. These researchers performed a computation to break discrete log on this exact curve.
All small characteristic pairing-friendly curves are insecure under modern knowledge. Here is another paper breaking discrete log on a curve over $\operatorname{GF}(3^{6\cdot 509})$ -- note that this field size is much bigger than your curve.


How to generate many passwords from one passphrase, so that knowledge of one password does not compromise the others?

You can just use a counter along with a key derivation function (https://en.wikipedia.org/wiki/Key_derivation_function) such as a hash, and do something such as:

for(int i = 0; i < numberOfPasswordsToGenerate; i++){
   aNewPassword = hash(MyWeakPassphrase + i);
}

The counter makes sure you get a new password, for each iteration of the loop, and they will never know the hash of the original passphrase without the counter.

Of course this can be brute forced, given a large enough dictionary for a dictionary attack or a good rainbow-table, so use a as well salt to prevent that... Actually, just always use a salt.

Edit:
To be clear on what I mean, this will make it more akin to this:

for(int i = 0; i < numberOfPasswordsToGenerate; i++){
   aNewPassword = hash(MyWeakPassphrase + i + salt);
}

The salt is just a large enough randomly generated number for each password you store next to the encrypted/hashed password in your database. If you just use a single identical salt for all the passwords, it is called a pepper instead, if I remember correctly.

Note: If you want to go further on security, you could use an IV (initialization vector) that contains the beginning number of the loop, so that the attacker has no idea which numbers you used, unless he gains knowledge of your IV as well.

This would look sort of like:

void generatePasswords(int IV) {
   for(int i = IV; i < IV + numberOfPasswordsToGenerate; i++){
      aNewPassword = hash(MyWeakPassphrase + i + salt);
   }
}

I'm bad at writing pseudo-code, sorry! It always get C-like, but yet not quite C.

Hope it helps!

NOTE: Please read Krystian's comment. We all suggest that you make different passwords by adding a counter and salt to it. This prevents precomputed attacks, but if someone learns the salt and counter (which can be expected, these are considered "public" knowledge security-wise), then they can bruteforce your primary password.
The fundamental problem here is that, you want to map a password to multiple unrelated values. In order to be able to recreate this mapping later on (which I assume you would want to, since you derive the passwords from the same passphrase), you need to make the passphrase different and still unique for each new password you make. We do this by adding a salt and counter. Since you need to store the salt and counter to recreate the mapping, they are considered public and thus anyone can still bruteforce your password, since it is weak.


How to determine the fastest OpenSSL cryptographic algorithm

It's always best to wipe disks using the ATA SECURE ERASE command directly to the drive. This command lets you wipe data that simply isn't visible to even the Operating System. It is a direct command to the drive to erase itself. Preferably you should send this command over a real SATA or PCI-e (M.2) connection as some (USB) controllers may get in the way. On Linux you can execute it using the hdparm command that is e.g. available on the Parted boot disks or sticks. The good thing is that it doesn't require any CPU or bus speed; the drive just wipes itself at maximum speeds.

The SECURE ERASE command is the only command you should use on an SSD. If you just write to an SSD then - first of all - you won't reach any sectors that have been written before due to wear leveling. Second, by writing data to all sectors, you'd mark all those sectors as in use, and you'd have to SECURE ERASE the disk anyway to be able to (reliably) use it again. Never try to wipe an SSD by just writing to it. Advantage: SECURE ERASE just erases the flash blocks, which is a separate, fast command to each of the blocks; it may literally finish in less than minute, even for larger drives.

Unfortunately, these commands may however be buggy, so some tests afterwards may be in order if you cannot find any information on the drive if SECURE ERASE has been implemented correctly (if unsure, buy Intel SSDs, as they have very rigorous testing of their drives - at least they seem most thorough when it comes to the security / drive encryption).

I don't think you will find anything much faster than AES-CTR on a highly optimized OpenSSL library. You could try a stream cipher as no Raspberry has fast AES support - as far as I know. For just erasing a disk I would assume that RC4 would give you much better results. It won't be as secure, but as it is exceedingly hard to remove data from a wiped disk in the first place, I'd say RC4 is still plenty secure none-the-less. So on actual hard drives - the type with actual disks - RC4 could be a preferred option.

The newer the disk, the more dense the data, the harder it is to restore it. So if you have a rather new disk then writing zeros may already be a good option. There may be some magnetic residue left on the outside of the tracks, but you'd have to reposition the head and be extremely lucky to be able to read it out with any chance of getting significant data. Most disk restoration services will not be able to restore a zeroed disk, at least as far as I've been able to find out so far.

Completely off topic here, but for dd, you'd probably better try a larger block size of e.g. 4 MiB using the -bs command. Otherwise you may get sub-optimal results.

I've got no idea on how to secure erase a USB stick or SD-card. They are pretty small, so if they contain any important data, I'd say destroying the chips physically is the best option. A direct appliance of a sharp object to the center of the chip destroys them with a very high reliability. They are very brittle and don't like torsion - or hammers, for that matter. Buy physically small ones so you don't pollute as much when you bin them for incineration - preferably only the silicon (the flame retardant in the plastic of USB sticks is highly toxic when burned; they are chemical waste).

Hammers also work pretty reliably on the disks of HDD's (with glass disks), for your uber highly secure stuff. Sanding them down is 100% effective. Wear protective glasses and protect yourself from dust and flying objects. I haven't tried this myself yet unfortunately.


When using AES-CBC-128, what attacks become feasible as you decrease the entropy of the IV?

Decreasing entropy of IV doesn't just allow any attack. You can have IV entropy of 0 and if you send just one message using one key, you are safe as you used full 16bytes of entropy on IV. Deciding how big IV you need is based on how many messages attacker can see with same key and how big of problem such IV reuse is in your case.

But, as you send more messages smaller IV have problem that there is chance for collision in IV, which allows attacker to distinguish same starting blocks in ciphertext. So if you send two ciphertexts "message1" and "message2", attacker would be able to see that both ciphertexts started with some common start and then it changed. He won't be able to learn what that common start was, and if messages were same after first change, he won't be able to detect those. So it will only grant attacker minor help in breaking your cryptosystem.

Another problem that isn't directly related to size of IV, but it's predictability is choosen-plaintext attack. If your IV changes in predictable enough way and you have access to service that encrypts data with predictable IV, you can xor first block of your message with IV of message you wish to decrypt and with IV you predict to check if encrypted message was encrypted already. So if your IV is predictable, you can check if ciphertext X was encryption of plaintext P you have, even if they have different IV's.

So basic problem with smaller IV is that you increase chance that you will reuse it, which is only small problem in cbc. You should too make steps to make sure it isn't predictable. But beware: IV reuse attacks can be far more devastating, for example in ctr mode.


What is the border between an ideal functionality and a protocol?

There are conceptual errors in the question. Protocols define how parties should interact among themselves and with ideal functionalities (so, it does not make sense to say that one protocol requires parties to interact with another protocol). Moreover, an ideal functionality describes abstractly the behavior of something, while a protocol describes how this behavior is achieved (protocols realize ideal functionalities). Finally, in the description of a protocol the number and the level of abstraction of the ideal functionalities that are assumed as available is up to the designer.


Found an answer here:

For each group of 256 plaintexts, this filter rejects 255/256 of all
wrong key guesses. As we guess a total of nine key bytes, we will need
10 or so groups of 256 encryptions to find the key.


Does it make sense to have a compression function that uses 64-bit of the message to create an output of 64-bit?

This hash function has a 64-bit output.  Therefore, it is not collision-resistant.  It is easy to find a collision in any hash function with a 64-bit output.  Since this appears to be a homework, I'm going to leave it to you to figure out why this is the case.

In general, please don't just post a homework question and expect us to solve it for you.  We're not here to solve your homework for you.  Instead, the expectation on this site is that you will show us in detail what you've tried and how far you've gotten, and explain where you got stuck.  Then we might be able to help get you unstuck.  But just posting the problem description from your homework, nothing more, and expecting us to hand you the solution on a platter is not what this site is for.  This isn't a "solve-your-homework-for-you" site.


Open source implementations of Symmetric Searchable Encryption and Order Preserving Encryption

cryptdb has these implementations inside it . But their licensing is not Open sources as in GPL etc . They say its available for research purposes !

I have implemented Symmetric Searchable Encryption in Java, its LGPL


Can you help me understand Format Preserving Encryption?

I cannot understand what is the difference with monoalphabetic substitution and what is the security offered.

A monoalphabetic cipher applies to individual symbols of the plaintext.  But an FPE scheme works on the whole message as a unit.  In the set {0,...,N-1} that you mention, N is the size of the message space—the number of distinct messages, not the number of distinct symbols; each number represents a distinct message, not a symbol of a message.  So for example:

For US Social Security numbers, which are 9 digits, N is one billion, and each number in the set {0,...,N-1} stands for a distinct SSN.
Credit card numbers have 16 digits, but generally the first 6 and last 4 digits must be left in the clear, so the middle 6 are encrypted and N = one million.

But the 10 digits left in the clear are used as a "tweak" to the encryption, so that 123456 in the middle six encrypts to different values for different credit card numbers.

The way FPE works is (ignoring the "tweak" concept that I mentioned above):

You define a bijective function between your message space and the set {0,...,N-1}.  For SSNs, N = 1,000,000,000, and the bijective function just treats the 9-digit sequence as a decimal numeral with its most significant digits padded with zeroes.
The FPE scheme gives you a bijective encryption function that takes a secret key and a number between {0,...,N-1} and outputs another number between {0,...,N-1}.  (It also takes a tweak, but I'm ignoring that for simplicity.)

So to encrypt an SSN you convert the SSN into a number using the function from (1), encrypt that number using the FPE scheme, and convert the encrypted number to an encrypted SSN using the inverse of the function in (1).  To decrypt you use the inverses of the functions.

One of the reasons why FPE scheme is defined in terms of sets {0,...,N-1} for user-chosen values of N is for flexibility; as long as you can define a bijection between your message space and such a set, you can use FPE to encrypt those values.  For example, if you want to apply FPE to a database date field, you can't just read the date's sequence of digits as a number, because some such sequences of digits aren't valid dates (e.g., 2014-54-35), but the encryption could well output the number 20,145,435.  But you can use date arithmetic to represent a date as a count of days since a reference "beginning of time," and then apply FPE using this bijection.

The security offered gets a bit more complex, but at the most basic level it is that the FPE is a pseudorandom permutation on the set {0,...,N-1}.  Imagine a solution where instead of using a cipher, you had a big database where, for each plaintext Social Security number, you stored a unique, randomly chosen sequence of nine digits.  The encryption operation would go somewhat like this.  Given a plaintext P:

Search the database for an entry that has P as its plaintext.
If P is already associated with a ciphertext C, then return C;
Otherwise, set C to some message chosen at random (using a true random number generator).
Search the database for an entry that has C as its ciphertext.
If C is already in the database, go to 3.
Otherwise, store the entry (P, C) in the database, and return C.

FPE's basic security goal, put in simplified terms, is to be no worse than that in practice, from the point of view of an attacker who has doesn't have the encryption key but might have seen a subset of the plaintext/ciphertext pairs.

Note as well that there exist token vault solutions that work like the six-step sketch that I described—a database that associates plaintext with unique random values.  So in another sense, the security goal of FPE is offer comparable practical security but at lower cost and better reliability and performance.


Authentication protocol which detects client impersonation from another machine

There are a few issues with your protocol. Namely it doesn't protect against men-in-the-middle.

Issue #1 (mentioned by fgrieu in the comments): Assume I host one of the (many) servers all your IP packets have to travel through from ClientA to Server. If I drop the server's Key1A (or KeynA) any future request won't work and I have successfully denied your user the usage of the server. He will have to re-perform the secure initial secret exchange which is likely expensive.
While this won't break the protocol in the sense you're interested in, this is still potentially harmful as it may cost you money (by losing customers being angry about the unrelieability of your protocol) if you need to do an expensive renegotiation (which involves human interaction?) too often.

Issue #2: If I don't just drop the packet, but flip a single bit, the client will get a wrong key and the server will assume the client has been successfully broken, so your legitimate client will be angry at you and has to re-perform the secure exchange. (see issue #1)

Issue #3: If I can eavesdrop on any of the server's responses and I'm able to drop all users packets, I can successfully take over the role of the client.
You send the next valid token in each of your server's responses and if I can get my hands on that and one valid client request (for getting the ID) I can successfully use said ID and the valid token to make my own requests.
All I have to ensure is that the client won't make any requests himself until I've finished all my evil requests.
The time-frame I need may be relatively short (a few seconds or minutes maybe) and I may be very well able to pretend the server is offline for maintenance for this time-frame. Or I could just launch a packet flooding attack on the client (which probably doesn't have more than 100Mbps bandwith?).
You shouldn't rely on an attacker not being able to DoS your client just because "it's not easy", a good protocol wouldn't create this situation in the first place (and the below mitigation should fix this issue anyways), for example you could avoid sending the next valid token at all,
but cleverly use HMAC to only send derived values and thereby only send the next valid nonce.

Issue #4: If the client actually is some piece of software that should authenticate to the server, I as the (not-so) legitimate user can extract the full program state from RAM / disk drive and just copy it over to another machine to perform my evil requests from there, and maybe I even install some software (like increasing packet loss or just root-level blocking the application) to make sure the legitimate client needs some time to figure out, I stole his credentials. This will be detected, but I still have some time (minutes up to days) to make my evil requests which may cause serious harm to the system and make you lose customers / money.

I hope this points the main issues of your protocol out (if anyone finds any else, please comment / answer yourself).

Now for the improvement.

The best thing to do is: Don't roll your own crypto.

The easiest way to mitigate the issues #1-#3 is by simply using your protocol on top of server-authenticated TLS. This would mean a modified packet would never reach your client application, the server would notice (thanks to record numbers / TCP) if a key didn't reach the destination and an eavesdropper wouldn't be able to read the valid tokens (and mitm is mitigated if the client checks the certificate properly). To fully mitigate man-in-the-middle attacks, you have to deploy DNSSEC along with TLS (and maybe DANE if you're at it) which would ensure you get the correct IP from the domain name for which you know the correct certificate (and can cross-check via DANE) and would allow you to drop the "known IP" requirement.

Issue #4 can't be mitigated with a pure software solution. I can go ahead and copy the state of any program (if I'm root / admin on a PC) and continue running it somewhere else (at least for some time). You need to use a hardware solution in order to ensure that a specific PC was used for a specific client or the client will be able to just shut-down his PC and copy the app to another one (in the same network?) and run it from there. The cheapest approach to this is using the TPM many modern PCs have (and which Windows 10 will require as of july 2016 for Windows 10 logo certification of PCs)


Signature and Timestamp for Long Term Document Archival Question

Time stamps are also signatures; see for instance RFC 3161 which is the most commonly used time stamp format. In particular, such time stamps also rely on certificates (the TSA certificate), and thus also expire.

So you need regular time stamping; whenever the latest time stamp is about to expire (but before expiration), you need to obtain a new time stamp computed over the previous time stamp. Such chaining is described in several standards, including PAdES (which supports embedding signatures and time stamps within the PDF file itself); a somewhat clearer description of time stamp chaining is Evidence Record Syntax.

To survive unexpected loss of a TSA before the time stamp expiration date (e.g. due to a compromise), you can use several TSA and interleave them in the chain: you get a time stamp from TSA A, and immediately after another time stamp from TSA B (computer over the time stamp from A). Whenever either time stamp is about to expire, expand the chain with two extra time stamps, again from A then from B. With interleaving, you can survive the loss of either TSA (but, of course, not of both).


Mathematics behind end-to-end encryption

End-to-end encryption refers only to the -- somewhat tautological -- fact that encryption happens on both ends and any intermediates do not have access to the keys, not to the specific math behind it.
Since the keys have to be available to both ends, public key cryptography is usually the preferred method, because the private key for each end is not transmitted to the other end, and therefore cannot be intercepted unless either end is compromised.

Also wether it is factoring-based (i.e. RSA algorithm), or elliptic-curve based refers to the method of getting the function leading to the encrypted message, which is difficult to reverse.

The basis of cryptography is quite algebra-heavy, depending on your background; that said one introductory book is  Hoffstein's: springer.com/us/book/9781493917105

Either way it's probably easier than going through the original literature on the topic. Otherwise, you may want to start with a more conceptual primer, here's one

https://blogs.msdn.microsoft.com/plankytronixx/2010/10/22/crypto-primer-understanding-encryption-publicprivate-key-signatures-and-certificates/

https://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

hope that helped.


Security considerations on "expand 32-byte k"-magic number in the Salsa20 family of stream ciphers?

Salsa20 has strong rotational symmetry. The main point of these constant is that they're not invariant under rotations, introducing an asymmetry. The precise value isn't very important, as long as it's sufficiently asymmetric.
Bernstein - Salsa20 security says:

Notes on the diagonal constants

Each Salsa20 column round affects each column in the same way starting from
the diagonal. Each Salsa20 row round affects each row in the same way starting
from the diagonal. Consequently, shifting the entire Salsa20 hash-function input
array along the diagonal has exactly the same effect on the output.

The Salsa20 expansion function eliminates this shift structure by limiting the
attacker’s control over the hash-function input. In particular, the input diagonal
is always 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574, which is different
from all its nontrivial shifts. In other words, two distinct arrays with this diagonal
are always in distinct orbits under the shift group.

Similarly, the Salsa20 hash-function operations are almost compatible with
rotation of each input word by, say, 10 bits. Rotation changes the effect of carries
that cross the rotation boundary, but it is consistent with all other carries, and
with the Salsa20 operations other than addition.

The Salsa20 expansion function also eliminates this rotation structure. The
input diagonal is different from all its nontrivial shifts and all its nontrivial
rotations and all nontrivial shifts of its nontrivial rotations. In other words,
two distinct arrays with this diagonal are always in distinct orbits under the
shift/rotate group.

Another relevant document is the somewhat ranty Response to "On the Salsa20 core function".
SipHash shares some design principles with Salsa20 and has a similar constant.  The SipHash paper explains the choice of values:

Choice of constants. The initial state constant corresponds to the ASCII string
“somepseudorandomlygeneratedbytes”, big-endian encoded. There is nothing
special about this value; the only requirement was some asymmetry so that
the initial $v_0$ and $v_1$ differ from $v_2$ and $v_3$. This constant may be set to a “personalization string” but we have not evaluated whether it can safely be chosen as
a “tweak”. Note that two nonzero words of initialization constants would have
been as safe as four.

Would it make sense to change this magic string to a different value?
Keep it unchanged. There might be some rare scenarios where it's useful to customize the constant, but in general you should not.
In response to a question on the CurveCP mailing list, Bernstein wrote:

Is there a recommendation to customise sigma per application ?

No.


If the moduli share no commonness / weak properties, it's impossible to solve the problem as given at hand. (As CodesInChaos pointed out)

Now as you're given RSA moduli, which are always constructed as $n=pq$, you can be sure that if you find $gcd(n_1,n_2)=R>1$, than either $R=p$ or $R=q$ must hold.
As you pointed out in the comments you indeed found such an $R_1$ for $n_1,n_2$. Now you reconstruct $P_1=n/R_1$ and check if $P_1*R_1=n$ holds, which is the case.
In the next step you check wether $P_1$ or $R_1$ divide any of the other moduli.
If it does, you reconstruct the other prime of these moduli via $n/R_1$. You repeat this procedure for all factors you're given.
As soon as you've done this step and still have unfactored moduli left, you try to apply the GCD on all pairs of unfactored moduli and use the resulting factors to obtain the remaing factors and factor the remaining moduli.


How are calculated numbers in AES S-box?

You forgot to compute the inverse of 02 first. The inverse of 02 is 8d (as $02 \cdot 8d = 01$ in the AES $GF(2^8)$ representation). You then apply the affine transform to the value 8d.


How to convert from small field to large field

I think that what the OP is thinking about is a $(2,2)$ additive secret-sharing scheme in which a secret $S$ is split into two shares $X\neq 0$ and $S-X\neq S$. Here, $X$ is an arbitrarily chosen nonzero integer. Neither share holder can determine the value of $S$, but when both shares are submitted to the trusted reconstructor, the reconstructor can recover $S$ as the sum of the two shares.  In the OP's scheme, $S=2$ is split into shares $3$ and $4$ where right-handed folks can assume that $X=3, S-X=4$ while left-handed folks can assume that $X=4, S-X=3$ and all of these elements are assumed to be elements of $\mathbb F_5$. Thus, the secret $S = (X) + (S-X)$ (which has value $7$ in ordinary integer arithmetic) is also  an element of $\mathbb F_5$ and works out to be the correct value $2 \in \mathbb F_5$.
The OP then wonders

Assuming that the secret $S$ continues to have value $2$, what should the share values $a$ and $b$ be so that $a+b = 2\bmod 500$?

Note that we do not necessarily have to have a field of order $500$ (as the OP mistakenly assumes exists) for this simple additive secret-sharing scheme; the additive group $\mathbb Z_{500}$ will work just fine. So, the answer to the OP's query is that the share values can be any two integers whose sum is $2$ modulo $500$. For example, the shares could be $(a,b) = (3,499)$ or $(a,b) = (498,4)$ if we choose to keep one of the two share values the "same" as before; with quotation marks around same to remind folks that $3,4,498, 499$ are elements of  $\mathbb Z_{500}$, not $\mathbb F_5$. It is, of course, an added bonus that $a+b\mod 500 = a+b \mod 5$. But other choices would work equally well; $(a,b) = (251,251)$ will stop juvenile bragging rights arguments among share holders ("neh, neh, ni, neh, neh, my share is bigger than yours!").


How can C rand() be exploited if a secure seed is used?

The ISO/IEC 9899:1990 edition of the C standard contains:

  EXAMPLE     The following functions define a portable implementation of rand and srand.

static unsigned long int next = 1;

int rand(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

void srand(unsigned int seed)
{
    next = seed;
}

The state of this generator is entirely characterized by the 31 low-order bits of variable next. If we "generate a random number using LavaRnd to seed srand(), then generate some big key with rand()" as in the question, then only $2^{31}=2147483648$ outcomes (at most) are possible for the "big key", determined entirely by the 31 low-order bits of input seed.

That then allows an attack that tries all these keys. If testing a key requires $2^{20}$ clock cycles (about a million) of a $2^3$-core CPU running at $2^{31}$ Hz, the attack is expected to last $2^{31+20-3-31-1}=2^{16}=65536$ seconds, that is less than a day.

Depending on what's done with the "big key", there might be much faster attacks. For example, that would be the case if rand() is also used to generate the Initialisation Vector, which customarily is at the start of enciphered messages. A simple attack can find the value of next from three consecutive values of rand(). That takes literally less than the blink of an eye, and allows finding effortlessly all past and future output of rand() not interrupted by srand().

On the other hand, perhaps the above $2^{20}$ cycles estimation is way too low (that could be the case for an RSA key). But by any measure, a 31-bit keyspace is farther waaaaay too low. Currently, the threshold of practical security is somewhere near 80-bit, give or take 20. 128 is considered fine till 2030, except if one believes in fairies or quantum computers becoming usable for cryptanalysis any time soon.


An important principle in cryptography is "key separation" which holds that one should "use distinct keys for distinct algorithms and distinct modes of operation".  Violating key separation often opens up avenues of attacks that may break confidentiality, integrity, or even recover the key.

You can use a KDF to derive cryptographically independent keys from a single "master key", and then use those keys in different algorithms and/or modes, thus respecting key separation.

The paper "On the importance of the key separation principle for different modes of operation" (Gligoroski et al) provides the definition of key separation that I used above, and a description of some attacks that are possibly when key separation is violated.


Why is modulo being used for congruence in SHA-2 padding when the outcome is always the same?

We are given an $\ell$-bit message and we are trying to find the smallest nonnegative $k$ such that $\ell + 1 + k \equiv 896 \pmod{1024}$.  This means we are trying to find $k$ such that $\ell + 1 + k$ is 896 plus an integer multiple of 1024: $\ell + 1 + k = 896 + n\cdot 1024$, for some $n$.

Suppose you have an 895-bit message, $\ell = 895$.  A single bit of padding, with $k = 0$ zeros, makes its length a multiple of 1024 plus 896: $895 + 1 + 0 = 896 + 0\cdot 1024$.

Suppose you have an 897-bit message, $\ell = 897$.  The smallest amount of padding you can add to make it a multiple of 1024 plus 896 is 1023 bits, with $k = 1022$ zeros: $897 + 1 + 1022 = 896 + 1\cdot 1024$.

Another way to phrase ‘a multiple of 1024 plus 896’ is ‘a multiple of 1024 minus 128’.  The point is that we're adding the smallest amount of padding that will fill a 1024-bit block with room to append the length of the message as a 128-bit integer at the end.  The complete padded input is $$m \mathbin\Vert 1 \mathbin\Vert 0^k \mathbin\Vert \operatorname{be128}(\ell)$$ where $\operatorname{be128}(\ell)$ is the 128-bit big-endian encoding of the integer $\ell$, and $0^k$ is as many zeros as you need to make this an exact multiple of 1024 bits long.

We want an exact integer multiple of 1024 bits in the padded message so that we can break it into blocks $b_1 \mathbin\Vert b_2 \mathbin\Vert \cdots \mathbin\Vert b_n$ to compute $$f(f(\dots f(f(\mathit{IV}, b_1), b_2)\dots), b_n),$$ where $f$ is the internal compression function defined on a 512-bit state and a 1024-bit block, and $\mathit{IV}$ is the standard initialization vector.


Cryptographically linkable random tokens

I see 2 options that fit the requirement (small, verifiable within some limit).

Because the sizes are small, the probability of the collision of a random value showing linked is high, larger values will obviously help.

Option 1 is to have a random value, and encrypt or hash it, then truncate the result and concatenate to the original value. The size of the value limits the pool of available tokens, and the size of the truncated output limits the probability of a collision. For example:

$A$ is a random or sequential 14-bit value, $B = HMAC_k(A)$ truncated to 16-bits.
$A || B$ is a 30-bit (5 character base64 encoded) token that can be easily verified as being linked to $k$, with a pool of 16384 maximum tokens linkable to $k$

Option 2 is to encrypt the entire value using a block cipher, and limit the inputs to a small subset of the available plaintext space. Upon decryption, only values that fall into that space will be considered valid. The cipher must have a small enough block size for your application, which limits available choices to those designed for low resource systems, like SPECK with a 32-bit block size.


How long would it take to calculate the hash of a password by hand?

If you want a "quick" way of determining how long it will take for bcrypt-n10, you can process by hand a very very VERY small subset of its calculation, then multiply that time by how many times the algorithm will use it.
The round function is used many times, you can perform components just once to get a base time. There are operations on 32-bit values, you can just do 1.
There are 3072 round operations after key setup (64x16x3)
There are 521 round operations per expand key
There are 539 32-bit XORs per expand key
There are 2048 expand keys per key setup
That gives you 1070080 round operations and 1103872 32-bit XORs
A round contains 2 XOR and 3 32-bit addition operations and 4 S-Box lookups, you can now break this into:
3,210,240 unsigned 32-bit additions
3,244,032 32-bit XOR operations
4,280,320 S-Box lookups (which change all the time)
64 blowfish key schedule operations (ignore, maybe it will add 3% to the time)
Moving tons of data around
If you were SUPER fast and could do an XOR in only 10s, an addition in only 20s, and an S-Box lookup in 10s, that is 4842 days calculating 8 hours per day, just for those operations.
You would still need to take into account how much paper it would take, transferring data from page to page when full, and the additional writing required, and the additional verification of operations to make sure you don't make a 1-bit mistake somewhere and screw the whole thing up. Just go ahead and double the time.
That is 26 years working 7 days a week or 37 years working 5 days a week.
It would probably take me at least that long to do it even if I had an electronic calculator that had hex input and an assistant or apprentice helping me to expand s-boxes and verify my work; there is no way my fingers could do that much work a day or work that quickly.
Out of the 365 million or so bit operations you need to perform, the allowed error rate is 0. How much extra effort would it take you to make sure you make no mistakes in calculation over the course of decades? So try it out, get 2 random numbers, do one addition and one XOR, and see if the numbers line up... or if it takes you more time.


Proving a secret is known without revealing it

What you want is the https://en.wikipedia.org/wiki/Socialist_millionaires
Problem.
This problem is orignally phrased as two people want to verify if they have the same amount of money without revealing anything more.
Alice has a value $A$ and Bob has value $B$ and they want to verify $A =? B$
without either side revealing anything more than the result of the check.
See the wiki page for algorithm description.


Why are key lengths in asymmetric algorithms typically longer than key lengths in symmetric algorithms?

Let's consider a cryptographic algorithm (e.g. encryption) that uses a key. The key is part of a space of possible keys; e.g. the space of all sequences of 128 bits, for AES.

There is a conceptual attack known as brute force in which the attacker simply tries all possible keys until a match is found. This attack "works" for all algorithms, so, in order to achieve security, the key space must be large enough to make the cost of brute force ludicrous. Traditionally, we prefer it when the space of keys has size 2128 or more (in practice, 2100 would already be way beyond the technologically feasible, but cryptographers just love powers of two).

Symmetric algorithm usually accept keys as sequences of bits, where any possible sequence is a valid key. Thus, they can achieve the minimal key space requirement with a minimal number of bits: with keys of 128 bits, you can have 2128 keys, and they are all fine.

Asymmetric cryptography, on the other hand, tries to achieve something "magic". Symmetric algorithms are just mangling bits together in a kind of complicated knot; for asymmetric encryption or signatures, the only known methods involve mathematical structures. A consequence is that if keys for an asymmetric algorithm have a length of k bits, then not all sequences of k bits are valid keys.

Furthermore, the strength of the asymmetric algorithm relies on the intractability of the unraveling of the internal mathematical structure; for instance, in RSA, the public key is (mostly) a big composite integer, and the internal mathematical structure is the factorization of that integer into its prime factors. Attackers then usually have much better attack methods than simply trying out all possible private keys. For instance, a very primitive attack on RSA would enumerate possible divisors for the modulus, one at a time: for an integer n, the largest non-trivial divisor must of no greater than the square root of n, meaning that the basic "trial division" factorization algorithm will factor a 256-bit modulus in time 2128, not 2256. And we know of much better factorization algorithms.

The raw consequence is that asymmetric keys usually need more bits to express themselves: due to the internal structure, not all sequences of bits can be valid keys, and since there is an internal structure, attackers have better attack methods than brute force, thereby needing larger things.

Notwithstanding, most of the "key size" business is traditional. For instance, in the case of RSA, we say "RSA-2048" to mean "2048 bits", but that's just the size of the modulus, which is only one of the elements of the public key. The complete public key is a bit larger (to give room for the public exponent, which is usually short). The private key itself can be reduced to about half the size of the modulus (in that case 1024 bits), since if you know the public key (modulus n and public exponent e) and a non-trivial factor of n, then you can rebuild all the elements of the private key. However, it is traditional (and actually standard) to save private RSA keys as a bunch of integers that, for RSA-2048, would amount to more than 9000 bits, not counting encoding overhead.

Thus, the notion of "key size" for a cryptographic algorithm does not necessarily correspond to the actual encoded size of either the public or the private key, and it is always delicate to compare key sizes between different algorithms. For instance, "256-bit ECDSA" is usually considered to be stronger than "2048-bit RSA", even though:

256 is lower than 2048;
RSA-2048 public keys will have size closer to 2100 bits, and private keys will be encoded over more than 9000 bits;
256-bit ECDSA public keys are normally encoded over 520 bits.

(Though a 256-bit ECDSA private key happens to be indeed a 256-bit integer — but with a strength somewhat equivalent to a 128-bit symmetric key, not a 256-bit, because of the internal mathematical structure.)


With an alphabet of 27 characters, the maximum number of characters that can fit into one plaintext block is equal to the largest integer less than or equal to $\text{log}(n) / \text{log}(27)$:

$$\bigg\lfloor\frac{\text{log}(59768553302699443)}{\text{log(27)}}\bigg\rfloor = 11$$

On the other hand, assuming the ciphertext is represented as a string of characters in the same alphabet, the minimum ciphertext length will be 12. This is because it will have to accommodate a maximum value of $n$, which is greater than $27^{11}$.


Are all block ciphers FPE (format preserving encryption)?

The formal definition of a block cipher is a function
$$
E_K(P) := E(K, P): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n
$$

The input and output spaces are by definition n-bit blocks, so the operation of the cipher in Electronic Code Book (ECB) mode is technically "format preserving".

That is not however what "Format Preserving Encryption" (FPE) generally refers to, nor does it mean that all block ciphers modes of operation are format preserving, nor that all symmetric encryption functions are format preserving.

NIST SP800-38G, which recommends FPE modes of operation for block ciphers, defines FPE as "Given any finite set of symbols, like the decimal numerals, FPE transforms data that is formatted as a sequence of the symbols in such a way that the encrypted form of the data has the same format and length as the original data."  In other words FPE is a function

$$
E_K(P) := E(K, P): K \times M \rightarrow M
$$

where M is not necessarily a block of bits.  For example M could be a 16-digit credit card number, or a Social Security Number.  The ciphertext - rather than being a block of bits - will have the same size and alphabet as the input; that is it will look like a credit card number or SSN.

A typical use of FPE is to selectively add data encryption to fields within legacy messages without modifying the message format or the validation functions of your legacy systems.

Many block cipher modes of operation cause ciphertext expansion - where the ciphertext is larger that the plaintext - are are not format preserving. Any mode that includes a checksum or requires a message-unique Initialisation Vector (IV) will cause ciphertext expansion.


Challenge / Response to Prevent Replay Attack - Using nonce as challenge

In general symmetric ciphers are not vulnerable to attacks with known plaintext. So in general it is perfectly possible to encrypt the previous nonce.

With multiple nodes it would be a good idea to include the identity of the sender / receiver in the challenge or at least in the poly 1305 based authentication. Otherwise an attacker may trick a node into authenticating a different node than intended.


MTI/A0: modular arithmetic or elliptic curves?

It is quite simple to convert MTI/A0 into an elliptic curve method. An implementation is here.


Is it safe to re-use the same p and q to generate a new pair of keys in RSA if the old private key was compromised?

No, it is not safe.

There are several methods to compute $p$ and $q$ from $n$, $e$ and $d$. See appendix C of this document.


Storing Parameters In Argon2 Hash As Potential Security Issue?

First, following the "next big thing" is not generally a good idea in the world of cryptography. You should strongly prefer battle-tested code and algorithms over new ones. In this particular case, consensus is mostly that Argon2 is highly unlikely to fall victim to attacks that make it worse in practice than scrypt, bcrypt, or PBKDF2, so you're not necessarily wrong to pick Argon2; just consider that your instincts should drive you toward more well-established, conservative choices when it comes to cryptography. You should also strongly prefer off-the-shelf algorithms and implementations over versions you've made custom modifications to; you are orders of magnitude more likely to make things weaker through a misunderstanding or a through a bug than you are to sufficiently address a real weakness. Think of it this way: if your concerns are based on something real, and they're as easy to address as you believe, cryptographers and authors of cryptographic libraries would already handle this for you.

Second, the parameters are required in order to recalculate the hash. If you specify different hardness constraints when initially hashing the password, you get out a different result. It follows that if you don't know those parameters when trying to verify the hash, you would have to try every combination of those parameters until you get lucky enough to stumble upon the result
If you have these parameters stored directly in your code, you technically don't need to keep them alongside the hash itself. However, these parameters should not be set in stone: they should be continually increased as memory gets cheaper and hardware gets faster. Some libraries let you do this dynamically by "calibrating" the computation the first time you instantiate the library, such that it uses some fraction of available memory and takes (for instance) 0.1s of CPU time.

In exchange for losing this flexibility, you gain a relatively minor benefit in security. If you're using Argon2 with reasonable costs (> 0.1s), it should take an attacker an impractical amount of time to recover all but the most trivial of passwords; running through the list of the most common 1,000 passwords against a database of 10,000 users would take more than ten days of CPU-time, and even here you're better off mitigating this by preventing users from using passwords from these lists.

Still there's an undeniable, if small benefit. Can we get that benefit without the downsides? Yes. Rather than hide the cost parameters (which don't constitute much in the way of entropy), you're better off computing an HMAC of the password before sending it to Argon2. By using a secret key and computing an HMAC first, you get to keep flexibility for your cost variables, but you also prevent an attacker from having any ability to test passwords unless they've also acquired the HMAC secret, which has far more entropy than do your cost parameters.

Edit: One other thing to note is that your suggestion doesn't really defend as much as you think it would. As I point out in my comment to @LuisCabrillo's answer, the sum of these things adds up to perhaps 16 bits of entropy. Against a smart attacker who creates an account on your site with a password they already know, you've done very little to stop them now: they know the password and the matching hash, so just need to run through each possibility once until they determine your algorithm and cost factors. Then they can attack your password database per usual.


Using date stamp down to milliseconds / ticks as a salt?

You're going out of your way to create more work for yourself, and introducing a vulnerability. It's not necessarily a huge vulnerability, but why bother?

To get a number string down to the millisecond - If you can guarantee that you'd not have two requests in the same millisecond.

You cannot have such a guarantee, not without doing very complicated things.

If your server is fast enough, it may take less than one millisecond to serve a request. Even if it doesn't now, maybe it will after a hardware upgrade.
Clocks are not always accurate. Just because you have a function GetCurrentTimeInMilliseconds() doesn't mean that it has millisecond accuracy.
The time can go backward if the clock is adjusted. Or if you use the local time rather than wall-clock time.
If you have multiple threads running on multiple processors, they will, from time to time, happen to serve a request at exactly the same time, no matter how much resolution your clock has.
If the same code is running on multiple servers, it's the same thing: they'll all be generating the same number at the same time.

Depending on the purpose of the salt, repeating a value may or may not be catastrophic. For a nonce or IV in encryption, it is often catastrophic. For password hashing, the attacker only has a small advantage if the salt is rarely repeated.

then go and prepend it to the saved hash - right? Otherwise, I can never check the hash against a known input.

Yes. This applies no matter how you generated the salt.

So making a super strong salt, with crazy random entropy to then go and store it right next to the data it's salted makes me think, is this wasted effort? Or theatre to seem great but really all you need is a unique piece of data to provide the salt?

You don't need “crazy random entropy”. You just call GenSecureRandom() or whatever your function to generate cryptographically secure random bytes is called. This is less complicated than the date-based approach you propose!
Even better, when hashing a password, the password hashing library should take care of generating the salt. But if you're stuck with an old API that requires you to do the work, then just generate a random salt of the length stated in the documentation of the library or of the password hashing algorithm. This is the simplest method.


Security of a custom AES-based attack model

I'm guessing from your description that you are describing a mode of operation where $A$ is the message and $B$ is an IV/nonce for a specific block. However you seem to have made an exception where the attacker can know the ciphertext both with and without the $B$ involved. As such, you have a rather weird use of the cipher. To generalize to an arbitrary block cipher:

$ENC(A, K)$ reveals the ECB mode ciphertext
$ENC(B, K)$ reveals the uniqueness of $B$
$ENC(A \oplus B, K)$ reveals the ciphertext using a proper mode of operation.

As such, you essentially have an overcomplicated ECB mode with random inputs. The value $B$ becomes irrelevant to an attacker knowing $ENC(A, K)$. If an attacker needs to find $B$, however they can use the same ECB breaking since they also know $ENC(B, K)$.
This system is strengthened by the fact that $A$ and $B$ are both pseudo-randomly generated (hopefully in a secure manner), and as such normal attempts to break ECB would be useless. Your system also is indistinguishable from random for any number of encrypted blocks, since your input is actually random.
With your system it is impossible, assuming you use a secure encryption algorithm (AES is generally accepted to be secure) to obtain any useful information about the inputs faster than brute-force, even with ECB mode; except in the case of repeating inputs, at which point statistical analysis becomes possible. But for random inputs no statistical analysis is possible.
The only issue I see with this model is the sketchiness of your system - why would your system ever need to reveal $ENC(A, K)$, $ENC(B, K)$ and $ENC(A \oplus B, K)$? I'll leave that for you to decide.
I'm thinking you mean a kind of OTP where $A$ and $K$ make a private key used to generate authentication codes verified by a server also knowing $A$ and $K$... It doesn't really matter, I'm just trying to see if I can guess your intentions.


Diffie Hellman(DH) is a key exchange method, it is not a encryption/decryption algorithm.
You have to use the secret key generated from DH in a symmetric cipher algorithm which is the algorithm used to create ciphertext from plaintext in the first place.

For example, lets say Alice and Bob make a DH key exchange to generate a secret key $K$, then Alice uses that key to send a message $M$ to Bob by encrypting it using an encrption algorithm such as AES. So Alice creates ciphertext $C =AES_{Enc}(M,K)$ and Alice sends $C$ to Bob. Then Bob takes ciphertext $C$ and decrypts it using the same algorithm and the same secret key that Alice used to get the message: $M =AES_{Dec}(C,K)$.


Actually, one would be able to crack a $2n$-bit RSA public key in $O(\pi(2^{n+1})-1)$ time.  However, $O(\pi(2^{n+1})-1) = O(2^n / n)$, and we already know how to factor $2n$-bit numbers faster than that.

Hence, even if someone could come up with such a list (and find some place to store it), it wouldn't actually affect the security of RSA.


Can the XOR of two non-collision-resistant hashes be collision resistant?

The answer to your edited question is "yes, it is possible".

As a trivial example, let $H$ be an ideal $k$-bit hash function.  Due to the existence of the generic birthday attack, $H$ provides only about $k/2$ bits of collision resistance — that is, an attack can, on average, find a collision after about $2^{k/2}$ hash function evaluations.  Denote the output of $H$, given the input $x$, as $$H(x) = (b_1(x), b_2(x), b_3(x), \dotsc, b_k(x)),$$ where $b_i$ denotes the $i$-th bit of the output.

Now define the $k$-bit hash functions $$H_L(x) = (b_1(x), b_2(x), b_3(x), \dotsc, b_{k/2}(x), 0, 0, \dotsc, 0)$$ and $$H_R(x) = (0, 0, \dotsc, 0, b_{k/2+1}(x), b_{k/2+2}(x), \dotsc, b_k(x)).$$

That is, $H_L$ is the same as $H$, except that the last $k/2$ bits of the output are replaced by zeros, and $H_R$ is the same as $H$ except that the first $k/2$ bits are replaced by zeros.

Now, clearly, either of $H_L$ or $H_R$ alone only provides $k/4$ bits of collision resistance.  If, say $k = 128$, then $H$ may still be considered practically collision-resistant (effort to break = $2^{64}$), but finding collisions for $H_L$ or $H_R$ would be trivial (effort to break = $2^{32}$).

However, by construction, $H_L(x) \oplus H_R(x) = H(x)$.  Thus, the hash function obtained by XORing the outputs of $H_L$ and $H_R$ is identical to, and thus equally strong as, the original hash $H$.

That said, this doesn't necessarily mean that the XOR of two hash function always has better collision resistance than the original hashes — in fact, it's easy to construct examples where the collision resistance of the XORed hashes is worse than that of either original hash.  (For a simple example, let $H$ be a collision-resistant hash, and let $H_A = H_B = H$.  The either of $H_A$ or $H_B$ alone is collision-resistant, but $H_A(x) \oplus H_B(x) = 0$ for all $x$!)

More to the point, for real-world hash functions, it depends on why and how the collision resistance of the original hashes is compromised.  In some cases, XORing two hashes might improve their collision resistance; in other cases, it might not, or it might even make it worse.


In what sense are silicon PUFs unclonable?

The answer lies in "complexity", but I do not believe they are unclonable in the explicit sense, but I can think of ways to get data out depending on how they are made.  It is easy for me to see "ROM" type gates under a SEM, and what PUFs buy you is that the structure is uniform but then you do not know the electrical characteristics.

In a PUF array, you give it some electrical input and you get a seemingly random, but repeatable output due to [PVT] (Process Voltage Temperature) of the devices 1. You could actually consider this just a huge lookup table of complexity of bit-width and clock depth.  A 32-bit number gives you a 32-bit number out at some clock of X.  The input is generally easily to get to, but the output is buried in the layout.  The output could completely be probed, but you would get an answer for a single input.  (on the reverse engineering side, I could make things current mode so I could not probe them because probing them would cause errors).  Now assume that you have a PUF array that takes a single clock and has a 32-bit output due to a single 32-bit input, that means you'd need a single 32-bit value in your ROM to emulate the PUF.  Otherwise, you need an entry for each clock and input vector.  If you have 32-bits of possible input, for one clock, you'll need $2^{32}$ entries in your rom, and it gets huge from there.

So, (1) If you a voltage mode circuit on the output, (2) have a single entry to map, and (3) have a semiconductor lab, there's no reason you could not get a single output and replace it with the ROM.


Case Scenarios where Identity Based identification (IBI) Scheme can be employed

Perhaps an extensible version of the Twitter blue checkmark scheme?
A trusted central authority (Jack) sets up a parameterised system that allows signing keys to be produced whose verification keys match identifiers. A Twitter service user (Lil Nas) sets up an account with Jack. Jack carefully verifies that Lil Nas is whom they claim (or simply allows them to select an unused identifier) and issues them with the signing key that matches their identifier. In addition to signing all of their transactions on Twitter so that anyone can verify the connection between the identifier and tweets, Lil Nas could also use the key to sign and validate transactions on other platforms such as TikTok or Instagram or DMs, uniquely tying the content to the owner of the account on Twitter.
Users only need the system parameters from Jack and a single signature verification to tie content to identifier, which is probably more lightweight and robust than PKI certificate-based solutions.


Fully Homomorphic Encryption - state of the art

I guess the latest real production grade homomorphic library is Microsoft SEAL, which implements the BFV and the CKKS encryption schemes.

I'm not a big MS fan. There are other options to explore:

HELib implements the BGV scheme with GHS optimizations.

NuFHE implements a GPU reference of fully homomorphic encryption on torus

Also checkout the open group site for homomorphic encryption.


Are specially designed fonts sometimes used in cryptography?

Is this something that exists and could be plausible?

Yes, things like that already exist and have even been used by well-known serial killers!
(So much for creating a dramatic intro – lol)

Monoalphabetic Substitution Cipher

What you are referring to, could be categorized as a classical “pigpen cipher”; a monoalphabetic  substitution cipher where graphical symbols are used. You might change the symbols and maybe even the way you encode things, but replacing text with symbols will always boild down to a simple, monoalphabetic substitution cipher.

Nowadays, you won´t find too many examples of it in action, but things looked different hundreds of years ago when a simple substitution cipher was able to baffle the masses. Yet, those days have long gone and suchs ciphers can now mostly be found in children's books on ciphers or “secret writing” gimicks packed in breakfast cereal boxes.

The rare exceptions to this rule are limited to things like (for example) the notes from the “Zodiac Killer”. But – all in all – the enigmatic charisma of “danger” and “death” provided more mystery to those notes than the usage of symbols… something which can be broken/deciphered rather easily, assuming enough data or information is available.

Modern Cryptography and Kerckhoffs' Principles

For better understanding: in modern times (and on this site), we tend to handle cryptography according to well-vetted rules… among them some which go back to Kerckhoffs' principles, which defines that a cipher algorithm should be made public (aka: regarded to be known by “the enemy”).

One of the reasons why some notes by the Zodiac Killer haven´t been deciphered yet, lies exactly in that area: the algorithm was never published and the data provided by the Zodiac killer did not provide enough information to deduct the actual contents of the ciphertext with absolute confidence.

Now, please don´t get me wrong. As someone who has professionally designed some fonts for advertising and other purposes, I am always intrigued by the idea of putting some visuals in communication. But I can´t help to share my two cents to spare you from walking the wrong path unwillingly:

Would it make sense from a modern-day cryptographical point of view to create such fonts?

No. Not if you actually expect them to provide any kind of real cryptographic security.
Would it be a nice hobby and find some fans nevertheless?

Sure… as long as you keep in mind you´ll most probably be spending more time creating the fonts than others (cryptanalysts, as well as “ye average” puzzle freaks) will need to break the ciphertexts created with them.

Let´s take your font idea and put it on the front page of a newspaper as you implied. That might work once. But the more you publish, the more data will be available and since we´re practically talking about a monoalphabetic  substitution cipher, it won´t take too long for the first people to decipher your stuff by “guessing” the keys (with merely a sprinkle of Cryptanalysis).

Especially, since you´re even limiting the security down to…

  26 peaks

… instead of the 256 “peaks” (= 8 bits = 1 unsigned byte) we work with in modern crypto.

As a simple rule of thumb: The smaller the alphabet, the easier the cryptanalysis!

I surely agree with you that one can hide a secret in the open. But as soon as someone knows there´s a secret to look for, security starts to fade towards zero. That´s where you need a secure cipher, and – whether we like it or not – fonts can not replace cryptographically secure algorithms.

Nota Bene

If you want to take a look around at the different fonts and symbols, use your preferred search engine to check on “cryptography symbols“ and co.

You´ll also discover your idea is already used and published in newspapers as (cryptographic) puzzles. There are even a few pages diving into such graphical ciphers. One of many: http://www.phantomgallery.64g.ru/shiphen/cod6en.htm


Should number of iterations of PBKDF2 stay secret?

Normally we store the number of iterations with the hashed password. In the same string actually.
This allows us to upgrade the number of iterations in a running system and in an interm phase have different passwords with different number of iterations.

If however you tried to keep the number of iterations secret, an attacker who knows the password for a single account could easily discover the number of iterations.

If we really can't tell the number of iterations an attacker would need to assume an upper bound and both do more interm checks but more importantly may continue longer then needed if his upper bound isn't tight.

I do not recommend trying to hide this information.


Can I crack an AES string if I have all these parameters?

Since there are only $16^6 \approx 16.8$ million keys, you can try them all and decrypt the message with each. In general you would have to know something about the plaintext to identify which of those decrypted candidates is the correct one.

In this case it is known that the message is English ASCII, so the top bit of each plaintext byte will be 0. The chance of an $n$-byte message succeeding that test by chance is $2^{-n}$, so with more than 24 bytes of data (as you have) it is likely you will find a unique key that decrypts it into ASCII. The padding could include a 1 bit, so you might want to ignore the last block until you've found the key.

Remember to try different modes of operation if the first doesn't work – there is an IV, so it isn't ECB. If the ciphertext length was not a multiple of the block size, it would likely be CTR mode, but yours is.


DH Key Exchange Protocol (one-out-of two)

For question 1, Alice computes $k_0 = B^a, k_1 = (B/A)^a$, and Bob computes a key $k = A^b$. If $c=0$, then $B = g^b$, hence $k_0 = B^a = g^{ab} = A^b = k$; else, if $c=1$, then $B = Ag^b$, hence $k_1 = (B/A)^a = g^{ab} = A^b = k$. In any case, both players have a shared key (either $(k_0,k)$ or $(k_1,k)$).

For question 2, let me give you some hints. Bob generates $B$ according to one of two distributions: (I write $b \gets_{\mathsf{R}} \mathbb{Z}_p$ to indicate that $b$ is taken uniformly at random over $\mathbb{Z}_p$), $D_0 = \{b \gets_{\mathsf{R}}\mathbb{Z}_p: B \gets g^b\}$ and $D_1 = \{b \gets_{\mathsf{R}}\mathbb{Z}_p: B \gets Ag^b\}$. What can you tell about those two distributions? Why cannot one distinguish them, even with unlimited computational power? Additional hint: $A = g^a$; what can be said about the distribution of exponents $a+b \bmod p$ when $b$ is taken at random from $\mathbb{Z}_p$, but $a$ is fixed?

For question 3, let us suppose that there is a player, Bob, that is able to compute both $k_0$ and $k_1$ with some fixed probability $\epsilon$ after performing a one-out-of-two key exchange with Alice. Suppose now that you are given a challenge for the computational Diffie-Hellman problem: you receive the description of a group $\mathbb{G}$, as well as a tuple $(g, X= g^x, Y = g^y)$. You break the CDH assumption if you manage to return $Z = g^{xy}$ with some non-negligible probability. Therefore, your goal is now to construct a $Z$ which will have a good probability (related to $\epsilon$) to be equal to $g^{xy}$, by interacting with Bob: you'll play a one-of-of-two key exchange with him, using carefully chosen elements from the CDH challenge instead of picking group elements according to the specification of the key exchange. Then, you'll reconstruct $g^{xy}$ with good probability using the keys $k_0,k_1$ that Bob returns (recall that they have a probability $\epsilon$ to be the correct keys).

I've given many details, so you should be able to figure out how to properly answer the question by now. If you are still blocked, if there is something you do not understand, please do not hesitate to mention it and I'll provide further insights.

EDIT: further insights for question 3.

Suppose now you received $(g, X= g^x, Y = g^y)$. We will play Alice's role in a one-out-of-two key exchange. As you remarked in your comment, we cannot gain anything from the values $B=g^b$ chosen by Bob - as it is chosen by the adversary, he can always compute it. However, we can gain something from the fact that Bob will compute both $k_0 = B^a$ and $k_1 = (B/A)^a$: we can deduce $A^a$ from that by computing $k_0/k_1$. Note that $A^a = g^{a^2}$.

Let me sum up: we have an adversary Bob, to which we can send some $A = g^a$ and who eventually returns two keys. At the end of the interaction with Bob, by computing $k_0/k_1$, we recover $g^{a^2}$ (with probability at least $\epsilon$, as this is the probability that both keys are correct).

So, we can now see Bob as an oracle which returns $g^{a^2}$ when we send it $g^{a}$. Given such an oracle, solving the CDH problem is a standard exercise. Can you see how it is done? The trick is simply: use the identity $ab = 1/2((a+b)^2 - a^2 - b^2)$. Now, from the "exponent squaring oracle" and $g^x,g^y$, you should be able to find out $g^{xy}$.

If you still do not see how to solve the exercise, I'll give you the entire solution, but it's way more interesting and useful for you if you figure it out for yourself.


Yes, in your specific case, $d=1031$ is the answer.

You can check it in the following ways:

Just try it out. Select some arbitrary messages, exponentiate with $e$, apply the modulus and exponentiate them with $d$. If this yields your original message number (like 20 or 5001) you know it's the correct $d$.
Factor $N$ using the exponent. You may want to use one of these algorithms for this. If you can factor this you can be sure to have the correct exponent. Note for the link: $m=e*d$

Now to the other ways there are for your case to find $d$.

Wiener's attack. $d$ is small meaning, Wiener's attack applies. You've used this fact successfully.
Brute-force. The parameters look so weak, that you can even just try out the $2^{16}$ values for $d$.
Factoring $n$. Using the quadratic sieve or a similar algorithm (provided by msieve or even non-dedicated tools) you can factor your 140-bit ($\approx 45$ digits) modulus within a relatively short time (seconds). After having factored $N$ you simply use the factorization to obtain $d$ from $e$.
As the distance between your primes isn't that large ($<2^{10}$) you can as well use Fermat's factoring method, which should yield the parameters $p$ and $q$ reasonaly fast. You proceed as above then.

So you see these parameters are extremely weak, so you shouldn't even think about using them in practice. But as they are so weak I'd guess this is some sort of homework, so it shouldn't be that much of a problem.


What are the relative merits of padding algorithms pkcs7, iso7816, and x923?

ANSI x.923 padding and the padding used within PKCS#7 are functionally equivalent. The last byte of the padding stream is the length of the padding stream. The difference is the value of the other bytes, which are all 0x00 in ANSI, and all the identical to the last byte in PKCS#7.

f4 93 d6.00 00 00 00 00 00 00 00 00 00 00 00 0d    ANSI X.923
f4 93 d6.0d 0d 0d 0d 0d 0d 0d 0d 0d 0d 0d 0d 0d    RSA PKCS#7

Neither has a large advantage over the other, except that a zero padded message can be "fixed" to ANSI padding by simply changing the last byte in many cases.

I do not believe that either one requires official verification of the padding bytes preceding the last byte to verify that they are correct per the standard, meaning the same algorithm can decode either scheme by simply looking at the last byte. The same algorithm will also decode ISO 10126 padding.
If used in an unauthenticated scheme, the bytes should be checked for correctness, since some attacker advantage could be achieved through their manipulation. Verification is done with bitwise OR against those bytes, which then must either equal 0x00 for ANSI or the length byte for PKCS#7 padding.
Both only support up to 255 bytes of padding.
PKCS is by RSA for RSA products and algorithms, and ANSI is a generic common standard by committee with the goal of interoperability.

ISO/IEC 7816-4 is a different story. It is more flexible and can technically support an unlimited length of padding bytes, however removal of the padding can be more computationally intensive. ISO/IEC 7816-4 padding places a single 0x80 byte after the message, then pads the rest with 0x00.
The padding scheme is also known as bit padding, as it simply places a single 1 bit after the plaintext, followed by 0 valued bits up to the block size; it therefore works for bit oriented protocols as well.

f4 93 d6.80 00 00 00 00 00 00 00 00 00 00 00 00    ISO/IEC 7816-4

By specification you must start at the end and work backwards, checking every byte until you hit 0x80. If you hit something other than 0x80 or 0x00 the message is assumed to be incorrectly decoded. With a small block size this is quite fast.
ISO/IEC 7816 contain the ISO/IEC standards for electronic ID cards like smart cards. Systems that use the standard have mandatory padding for encrypted data.

I have also seen what I called "rainbow" padding, which looked to be a hybrid of ANSI and PKCS7. The last byte was the amount of padding bytes, and the preceding bytes were that value decrementing until the message boundary:

f4 93 d6.01 02 03 04 05 06 07 08 09 0a 0b 0c 0d    ???

I have never seen it described by a specific name, but it may be removable by an ANSI/PKCS remover if the remover only takes the last byte into account.

As you mentioned, none of these padding schemes are perfect. Only IEC 7816 can support block sizes of 256-bits and larger, and ANSI and PKCS7 can be unpadded by a common algorithm.


Would it be a requirement that, given $f(k)$ and $c$, it is hard to rederive $m$?
If so, then what you are effectively asking for is a public key encryption system; your public key is $f(k)$, and your private key is $k$.
Such a method can be constructed from any public key encryption algorithm (but isn't any more efficient than the underlying pk algorithm).
If not, then it is easy; here is one construction:

Let $f(k)$ be a randomized function $f(k) = r || \text{hash}( r, k )$.
To encrypt, you compute $\text{Enc}(f(k), m) = r || \text{AES}( \text{hash}(r, k), m )$.
To decrypt, you compute $\text{Dec}(k, (r || c)) = \text{AES}^{-1}( \text{hash}(r, k), c )$


security of multiplicative secret sharing

There is no 0 in the multiplicative group $\mathbb{Z}_p^*$. By the definition of a group, every element must have an inverse. Thus, the unity in a multiplicative group is 1 and there is no 0.


For CBC, if the initialization vector is corrupted, can we still decrypt the message?

If the IV is send with the ciphertext rather than derived (this seems assumed, otherwise the IV is unlikely to get corrupted) and is indeed fully unpredictable the those bits that are affected cannot be decrypted (presuming that the bits are changed with a 50% chance). This is because decryption of the first block of CBC depends on a XOR with the IV to derive the plaintext. If the value of any of the IV bits is unknown, then the value of the plaintext is unknown as well, similar to the way a one-time-pad works.

However, the decryption of the other, unaffected bits is still fully possible. And any block after that only relies on the ciphertext block before it, rather than the IV. So most of the message would still be recoverable, regardless of what happens to the IV.

So basically, the answer is no this is not correct other than for the bits in the first block of the ciphertext / plaintext that are affected by the changes in the IV.


Unable to understand hash function representations

I'll review the standard mathematical notations used for $H_1:\{0,1\}^*\times\mathbb Z_p^∗\to\mathbb Z_q^∗$ , going from the bottom up. Hopefully, that will make the rest evident.

$\{0,1\}$ is the set with the two elements $0$ and $1$, known as Booleans.

$\{0,1\}^k$ (for some non-negative integer $k$ ) is the set of tuples with $k$ Booleans, or equivalently of $k$-bit bitstrings; it has $2^k$ elements. For example $\{0, 1\}^3$ (or equivalently, $\{0, 1\}\times\{0, 1\}\times\{0, 1\}$ ) is the set of all three-bit bitstrings: $\{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)\}$.

$\{0,1\}^*$ is the union of all $\{0, 1\}^k$ for all non-negative integers $k$, or equivalently the (infinite) set of all finite bitstrings. This set usually also includes the empty string.

$\mathbb Z$ is the set of (signed) integers. $(\mathbb Z,+,\cdot)$ is the (infinite) ring of integers.

$\mathbb Z_p$ (also denoted $\mathbb Z/p\mathbb Z$, especially in number theory which uses the notation $\mathbb Z_p$ for $p$-adic numbers) is the set of the equivalence classes of the equivalence relation "congruent modulo $p$" over $\mathbb Z$; that is, an element of $\mathbb Z_p$ is a maximal subset of $\mathbb Z$ such that the difference of any two elements in that subset is a multiple of $p$. By taking the smallest non-negative integer in each such subset (which also is the remainder of the Euclidean division by $p$ of any element of such subset), we can assimilate $\mathbb Z_p$ to the set of the $p$ non-negative integers less than $p$. $(\mathbb Z_p,+,\cdot)$ is the (finite) ring of integers modulo $p$.

$\mathbb Z_p^*$ is the subset of elements of $\mathbb Z_p$ (containing elements) having a multiplicative inverse in the ring $(\mathbb Z_p,+,\cdot)$, or equivalently coprime with $p$. An alternative definition is that $\mathbb Z_p^*$ is the maximal subset of $\mathbb Z_p$ making $(\mathbb Z_p^*,\cdot)$ a (finite) group. When $p$ is prime, $\mathbb Z_p^*$ is (assimilable to) the set of the $p-1$ positive integers less than $p$, and $(\mathbb Z_p,+,\cdot)$ is the (finite) field of integers modulo $p$.

$\{0,1\}^*\times\mathbb Z_p^∗$ is the set of (ordered) pairs with the first element of the pair in $\{0,1\}^*$ and the second element in $Z_p^∗$.

$H_1:\{0,1\}^*\times\mathbb Z_p^∗\to\mathbb Z_q^∗$ is a notation stating that $H_1$ is a function from the set $\{0,1\}^*\times\mathbb Z_p^∗$ to the set $\mathbb Z_q^∗$. That is, $H_1$ takes as input a bitstring $b$ of unspecified (but finite) length (possibly the empty bitstring), and an integer $i$ coprime with $p$ and defined modulo $p$ (that is, $i$ and $i+z\cdot p$ are assimilated and will produce the same result for all $z$ in $\mathbb Z$ ), and produces $j=H_1(b,i)$ coprime with $q$ and defined modulo $q$ (we can think of $j$ as a positive integer less than $q$ and coprime with $q$, or as the set of all integers having that remainder by the Euclidean division by $q$ ).


Yes, you are remembering correctly.  Yes, this is a reasonable method to find the key length.

The reason why this works is because, typically, the plaintext is not uniformly random.  For instance, rather than a random bit-string, the plaintext might be some English text, encoded in ASCII.  If $X,Y$ represent two random English letters, encoded in ASCII, then the expected value of the Hamming distance $\text{wt}(X \oplus Y)$ is maybe 2-3 bits.  In contrast, if $U,V$ are two random 8-bit bytes, then the expected value of the Hamming distance $\text{wt}(U \oplus V)$ is 4 bits, significantly larger.  If you look at sequences of multiple characters, rather than a single letter at a time, the difference becomes even larger.

How does this apply to your situation?

Well, if you have correctly guessed the key length, then your ciphertext consists of $X\oplus K$ and $Y\oplus K$ (as Dilip Sarwate explains), where $X,Y$ come from the plaintext distribution.  Now notice that the Hamming distance between these two is the same as the Hamming distance between $X$ and $Y$, namely, it is $\text{wt}(X \oplus Y)$.  As we explained before, you can expect this might be maybe 2-3 bits times the length of $X$ measured in bytes.
In contrast, if you guessed the key length incorrectly, then you're looking at ciphertexts of the form $X \oplus K$ and $Y \oplus K'$.  The Hamming distance between the two basically boils down to the Hamming distance between $U$ and $V$, where $U$ and $V$ are uniformly randomly distributed (since $K,K'$ are uniformly randomly distributed), and thus is $\text{wt}(U \oplus V)$.  As explained before, you can expect this should be approximately 4 bits times the length of $X$ measured in bytes.

So, as you can see, the Hamming distance is significantly less when you've guessed the key length correctly.

For a vaguely similar method, read about the Index of coincidence; you can expect it to be more effective in some cases, and less effective in others.


What is an efficient random number generation algorithm

Since the goal is to generate the salt for PBKDF2, there is no need for an efficient (as in fast) random generator: PBKDF2 is (purposely) compute-intensive. Further, in many uses of PBKDF2 (e.g. storing a password), the salt is generated once, stored, and reused many times, further lowering the concern over efficiency of the salt generation. As the saying goes: premature optimization is the root of all evil.

In this usage, you also do not need a precisely uniform distribution (as would be the case for a random generator used e.g. in a casino machine). The (extremely slight) bias of RC4 is not a concern in the context of salt generation.

In that context, by far the most important criteria is that the generator should have low odds of generating twice the same value. As shown by recent anecdote in the context of RSA key generation (also here updated), that's difficult to implement correctly, especially on network appliances. The essential problem is that different runs of any deterministic RNG (such as RC4 or ISAAC) will generate the same result if fed the same input. Thus what matters is the seed material of the generator, and if/how its state is preserved across runs.

Two simple implementations of a generator that does not repeat are

Increment a persistent integer (stored e.g. in a data base), then output it. The integer should be wide enough to never overflow, or the  number of runs limited.
Obtain the UTC time to some granularity, wait at least as long as that granularity, plus twice the maximum absolute value of the uncertainty of the source of time, plus one second (to account for leap second), then output the result.

Notice that both methods assume a single instance runs, and can be broken if the attacker can influence the system (reset the persistent integer, alter the clock setting...). And of course, these generators are predictable, not random generators. But assuming the availability of a single secret randomly-seeded Key, this is easy to fix: given the output N of a generator that does not repeat, output HMAC(Key,N).

Practical designs of good software RNGs combine seed material gathered using several techniques, including the above, CPU clock since boot, process time, RAM content at boot, hard disk and network latency, mouse position, keyboard presses and their timing, hardware serial numbers such as in hard disk and network cards...

For more in-depth discussion on the desirable properties and design of software RNGs, see yarrow. For physical design and testing, see e.g. Design of Testable Random Bit Generators.


NFC with AES : how works the exchange of key

As in most Smart Card systems using symmetric cryptography, the reader does not hold a key shared with a card. It somewhat holds a master key which, combined with a card identifier (e.g. some serial number), can produce a so-called diversified key, which is in the card. This is known as key diversification (diversification is derivation using a master key and device ID). This insures that even extracting a key from a card can't compromise the key of other cards.

The reader-side cryptography is typically performed by a SAM, perhaps similar to this one.

Thus UID/RID might be the device ID used for diversification. Or not. It is not secret, most often can be read (at least in EV1) and thus cloned; but the associated diversified key can not be read, and that's what prevents cloning.


The idea

  'deterministic predictable pseudo-random generator' where I can just ask 'give me the nth random number'

is already known, and there are some stream ciphers that work like this (like CTR mode of a block cipher, or the Salsa/ChaCha family of stream ciphers).
Usually they don't produce a single byte, but some larger block of consecutive key stream bytes, which is more efficient if you don't have single bytes to encrypt, and (as mentioned by user4982's answer) doesn't restrict you, as you don't have to use all these key stream bytes to encrypt/decrypt your piece of data.

I won't look at your specific cipher (it is too much on the code level for me), but it is probably not a secure one.

The idea itself (even when implemented with an perfectly secure stream cipher) has a problem when used for random access file encryption: You will be having (at several points of time) different pieces of data encrypted with the same piece of keystream, which then leads to the two-times-pad problem, if a potential attacker could look at your encrypted file at different points in time.

You'll need to reencrypt larger blocks with a new initialization vector to avoid this.


Do I understand (below) why Q = dP is easy while finding d is hard

Computing $d$ given $P$ and $Q$, with $Q = dP$ is known as the "elliptic curve discrete logarithm problem" and is considered to be infeasible under some hypothesis. The security of Elliptic Curves Cryptography is based exactly on the ability to compute the point multiplication and the intractability of the inverse operation: given two points find out the discrete operand $d$. The difficulty of the problem is given by the size of the elliptic curves.

One (of the best) algorithm to compute the discrete logarithm, Silver–Pohlig–Hellman algorithm, has complexity $O(\sqrt n)$ where $n$ is the order of the elliptic curve, but it is very efficient in the case of $n$ smooth (product of small integer). This is also the reason you don't want to have a curve with a smooth number as order.

The first part of your question shows a standard way to compute the point multiplication using the binary expansion of the multiplicand. It is usually known as "double and add" and corresponds to the "square and multiply algorithm".

If you're trying to understand how the backdoor in the Dual_EC_DRBG works you should read this answer  to the question  Explaining weakness of Dual EC DRBG to wider audience?. Roughly the $P$ and $Q$ used in the standard are generated in an unknown way. So, if NSA knows the $d$ scalar such that $Q = dP$ they can compute some values and synchronize with the generator. If you implement the same algorithm using two (provable) random points, the backdoor disappears. Usually a provable way to generate a point is to hash some not random english strings (as the US Constitution or the Shakespear's work or the Star Wars The Force Awakens original script, or ...) and use this output to generate the point.


what is the range for exponent e?

Actually, there is no required upper bound for $e$ (except that some implementations may reject ridiculously large values).  The math behind RSA states that any $e$ that is relatively prime to both $p-1$ and $q-1$ will work, no matter how large it is. There might not appear to be a need for an $e > lcm(p-1, q-1)$ (as for any such $e$ larger than that, there is a smaller $e$ that acts equivalently). However, there are obscure cases where such $e$ arise; one possibility is some shared computation of the RSA key pair (where no one entity knows the factorization) could possibly generate such a huge $e$ (depending on how that shared computation works).

  What is the max integer that can be encrypted?

Well, if you omit the padding, the largest value that can be encrypted is $N-1$, as Raoul722 states.  However, it is rarely a good idea to omit the padding in RSA (and if you have to ask, you don't know enough to safely omit it).


Can a service that can only sign text, be used for encryption/decryption?

The signature algorithm would need to be deterministic. Only PKCS#1 v1.5 based RSA signatures are deterministic; most other modern (and popular) algorithms use random input for the signature. If the signature is random then your encryption and decryption key will be different and the protocol will fail.

The random blob of data isn't kept secret (if you could keep it secret between the two parties you would not need the signing service). Anybody can access the blob. So anybody with access to the service will be able to generate the signature used to derive the secret key.

So (after the edit) the scheme could be used to generate a symmetric key. But beware that whenever the private key changes or whenever the private key is used for a different, non-deterministic scheme it will fail. If the signature is deterministic you could however generate a static shared secret and use that for further communications.

It's kind of obvious, but remind your self that the owner of the private key service will also be able to generate the secret key. You might as well randomly generate a secret and put it somewhere in the service. Then you would not be dependent on the private key being available (using keys for different services is severely frowned upon when it comes to key management).


In ε-differential privacy, ε represents the privacy parameter.

You might want to try to enhance your research efforts because related papers and publications mention that more than frequently.

Even websites like Wikipedia would have quickly provided you with an answer to your question. Quoting Wikipedia > Differential privacy > ε-differential privacy > Trade-off between utility and privacy:

  A trade-off between the accuracy of the statistics estimated in a privacy-preserving manner, and the privacy parameter ε.

(emphasis mine)

Beyond that, you could also take a good look at these Google scholar search results. The truckloads of related papers and publications presented there explain ε-differential privacy and tend to contain examples. Honestly, “simply” writing down an example would quickly become too broad since you‘ve obviously not yet invested any time to read about ε-differential privacy and I surely don’t want to write a book explaining everything (incl. notations) from scratch. But the pointers (links) I have provided should definitely help you get started on your quest for knowledge.