# Tag Info

A.Toumantsev had it right in his comment that 'it depends'; I'll try to expand on that. First of all, there's no one 'window method', there are a bunch of different variations, and which $w$ works best for you would depend on the exact version you're using. With the most basic window method, to compute $a^e \bmod p$, you: compute $a^0 \bmod p, a^1 \bmod ... 0 Window Size (W) for many practical implementation of RSA Algorithm (like OpenSSL) is related to key length.for example in openSSL library for insecure 80 bits key, W is 4 or for insecure 320 bits key , W is 5 and for 1024 or 2048 bits key (length), W is 6. note:Maximum of Window size in openSSL Library is "6" -1 Initially the prizes would have been useful to prove the safety of their system. However they have driven a lot of academic effort and in effect the prizes were deemed at some stage to be counter productive I assume. This would especially have been the case if someone has made a quantum computer and factored all of the challenges in at once: dramatically bad ... 3 Firstly, it's not co-prime to the modulus, so$\gcd(m,N)$would be greater than$1$. Secondly,$N$is the product of two (and only two) prime numbers$p$and$q$, so if$\gcd(m,N)>1$, then you know$m$is one of the factors (and prime factors) of$N$. 12 I've been suggested to digitally sign it, thus, I have my private key, and I ship my application with a public key, and the application then uses the public key to check the QR code As long as you can live with the requirements for RSA (signature size, computation), that sounds like an excellent idea. Am I encrypting the whole message using the private ... 4 To your questions: You are not encrypting anything. Signing something with RSA is basically the same algorithm as decryption but some things are different (see below). No. You can generate one keypair and then use it for encryption, decryption, signing and verification. To help you with your task: Getting this right is not easy. If you have no ... 12 From this answer: The difficulty of factoring (thus, as far as we know, the security of RSA in the absence of side-channel and padding attacks) grows smoothly with$n$. So, if factoring is the method of choice for breaking RSA, it doesn't seem like it really helps. 3 ASCII is one way to encode an alphabet into integers, which in return are mostly represented in binary or hexadecimal notation. But of course there are many other ways to encode alphabets into numbers, and exactly how you do that is entirely up to you. For example you just have the letters from A to Z and got the string$s = s_0s_1s_2s_3....s_n$. Then you ... 5 Say you want to encrypt "Hello World!" with RSA. The first important thing here is the encoding of that text. "Hello World!" as such cannot be encrypted since characters are a non-numerical concept. So an encoding is used convert the characters of that text to numeric values (e.g. the ASCII / Unicode table, but there are many others, especially for non-... 5 …what number do we have to put as$m$in the RSA formula? There are three possibilities what$m$can be. A full-sized random bit-sequence, e.g. a random sort-of-key which is roughly as large as the modulus and will be used to derive a symmetric key for message encryption. Some padded message. This would mean you'd first apply some padding to your message,... 3 It depends on the application if base 64 is being used to represent keys. Many applications that implement/use cryptography have been originally designed in a time where ASCII based communication was commonplace. If you would directly use BER / DER - a binary encodoing of parameters - then you had a high chance of losing data. For instance, you would not be ... 3 Base-64 is simply a way to represent binary data using the ASCII character set. It's used because a single base64 digit represents a whole number of bits (6 bits), where each decimal digit represents ~3.3 bits, which can make conversion a little tricky. Being able to represent more bits per digit also means its more space efficient than decimal. It takes ... 9 Your problem is equivalent to solving$m^3 \equiv c \pmod n$. This corresponds to breaking RSA for$e=3$. We know no efficient way for doing that without factoring$n$. If you know the factors of$n$you can compute the private exponent$d$as$e \cdot d \equiv 1 \pmod{\varphi(n)}$using the extended euclidean algorithm and then compute$m$as$c^d$. 3 Comments already pointed out, that encryption and signing are not the same and should not be exchanged deliberately. Of course in practice specifically for RSA, not PKE in general, and only in the textbook variant (no padding), encrypt/decrypt are bascally the same operations as sign/verify: For all of them, you just do modular exponentiations; and the ... 0 Your approach is correct. I will just point out that you get a bit more than integrity. Because you are using a signature you also get: authenticity: the data are from sender A and not sender B non repudiation: sender A cannot deny he sent this data. 0 I am afraid I was a little flippant in my comment to the first version of your question. Your edits have made for a more substantive question, so I feel I owe you a more substantive answer. It must be at least as hard as factoring to compute$d$because (as I will show below) if you can compute$d$for arbitrary$e$then you can easily factor. So ... 1 From RFC 2985: The challengePassword attribute type specifies a password by which an entity may request certificate revocation. The interpretation of challenge passwords is intended to be specified by certificate issuers etc; no particular interpretation is required. This has also come up over at Information Security Stackexchange with the TL;DR ... 4 It seems that the authors of Keccak sponge (the algorithm chosen to be SHA-3) do think their SHAKE functions can directly be used for simplifying OAEP and PSS: The introduction of extendable-output functions (or XOFs, pronounced zoff) is a particularly nice feature of the standard. A XOF like SHAKE128 or SHAKE256 can be seen as a generalization of hash ... 11 The digital signature algorithm encrypts a hash using the senders private key and the receiver's public key. Huh? I see two problems with the above statement; "Encryption"; using the word encryption implies that there's a way somehow to decrypt it. However, there's no way to anyone, even with the private key, to "decrypt" a signature to generate the ... 4 The first hash is only used to hash the label. Most of the time the label will simply be empty, which means that a constant value can be used, identified just by the hash algorithm itself. Although the hash values may differ and may have any SHA-x value, they are generally set to SHA-1 - which is the default. Note that SHA-1 is considered secure for MGF-1. ... 3 are the DH public values exchanged unencrypted? Yes, that are. After all, they are "public values"; there's no weakness in exposing them in the clear. Now, we do have to be careful that they aren't modified in transit (if they can be, then someone can perform a Man-in-the-Middle attack). We do that by having the server sign its key share (using the ... 0 This approach protects A and B from an external attacker who might want to mess with the message. However, it does not protect A from B or B from A. For example, A can craft a message and claim that it came from B since B is the only entity that shares this particular key with A. This property (called non-repudiation) is not unconditionally an advantage, ... 0 Usually symmetric crypto is preferred thanks to its efficiency compared with public key crypto. Its primitives are faster compared with those in public key encryption. There is is of course a tradeoff in key management: How users share their secret key in a symmetric setting? Asymmetric encryption solves this problem with the assumption of a trusted PKI, or ... 7 MACs have some advantages over digital signatures The component of the computational cost that is independent of message size is much higher for digital signatures, to the point of being an obstacle and requiring milliseconds or/and dedicated hardware. We know no signature scheme where both signature and verification of short messages are of speed any ... -2 Public keys may not have been exchanged yet between A and B (maybe all they have at that point is a pre-shared secret). 10 There are many advantages of MAC's over signatures. For signatures you need to use asymmetric key pairs. Public keys need to be trusted for this to work. Unfortunately establishing trust is not that easy. Furthermore you don't want to use a private key stored on, for instance, a smart card (which would require a PIN and would likely be too slow). Instead ... 4 Can someone quote a protocol, application, etc, where the disadvantages of the MAC relative to digital signatures can be ignored? Your particular attack is of no interest if B has nothing to gain to claim that it got message M from A. As for concrete examples: the TLS record format, IPsec, SSH, the IES public key system; actually, any protocol that ... 3 Since$e$and$(p-1)(q-1)$are relatively prime, the extended Euclidean algorithm gives you integers$u$and$v$such that $$eu + (p-1)(q-1)v = 1,$$ from which it is easy to deduce an integer$d$such that$ed \equiv 1 \pmod{(p-1)(q-1)}$. 0 Building such a table would be very difficult, because certificate-sizes depend on a lot of (variable-sized) things, including but not limited to: usage constraints signatures public keys URLs to CRLs and OCSP-servers Name, location and other identifiers of the key-holder Name, location and other identifiers of the issuing CA However, you can estimate ... 6 No, your values for$e$and primes are fine (well, at least for a toy example);$e$is relatively prime to both$p-1$and$q-1$, and that's the only hard requirement (not counting the security related ones, of course). I get$d=905$, as$5 \times 905 \equiv 1 \pmod{ \operatorname{lcm}((53-1),(59-1))}$; alternatively, you might get$d=2413$, if you do the ... 4 Well, there are indeed differences between the two standards, as you can see below: key pair generation X9.31 requires that$p-1$,$p+1$,$q-1$,$q+1$all have prime factors between$2^{100}$and$2^{120}$, and that$p$and$q$differ in at least one of the first 100 bits. These requirements are there to frustrate suboptimal factoring methods, ... 4 I2OSP and OS2IP mean Integer to (2, also pronounced "two") Octet Stream Primitive and Octet Stream to Integer Primitive. Note that the word "octet" simply means 8-bit "byte" and that "stream" can be replaced with "array". So these are conversion functions between non-negative integers to byte arrays. The I2OSP function simply represents an integer in a ... 3 That tells us those problems are in BQP. This answer describes a way of reducing factoring to SAT. More elaborate approaches will give reductions from ​ RSA or ECC ​ to SAT. On the other hand, if there is a polynomial-time reduction from an NP-hard problem to ​ RSA or ECC ​ ​ then ​ ​ ​ BQP ∩ UP ∩ coUP ​ = ​ NP ​ . 6 Due to poor use of notation, the question uses an incorrect (or at least incomplete) definition of textbook RSA encryption, which actually defines ciphertext$c$for a given$m$as:$$c=m^e\bmod n$$This can be read as: “$c$equals [pause]$m$to the$e$th power reduced modulo$n$” where power or/and reduced can be left implied, and the pause emphasizes that ... 0 You appear to be confused about a couple of different things, at least if I have correctly interpreted your confusion. First, the relation you should be using is congruence, not equality. The encryption congruence (not equation) is thus more precisely: $$c \equiv m^e \pmod n$$ Note that this uses the triple congruence sign rather than the equals sign. ... 1 RSA is based on the Carmichael function$\lambda$(or if you prefer Euler's totient function$\varphi$): $$x^{\lambda(n)} \equiv 1 \pmod n$$ for every integer x that is coprime to n. From this you trivially get: $$x^{k\lambda(n)} \equiv (x^{\lambda(n)})^k \equiv 1^k \equiv 1 \pmod n$$ and multiplying both sides with x: $$x^{k\lambda(n)+1} \equiv x \... 0 You forget that there are relationships between n, d and e. If you forget those then you basically forget to include the entire RSA problem. 5 So if m^e can be greater than n, then you can get duplicate ciphers for the same message. I'm not exactly certain what you mean, but: If you mean that one particular message m might be encrypted in two different ways, no, that's not the case, at least, not in the way that you mean. If you have a specific value for m, e and n, then m^e \bmod ... 5 The formula at the heart of RSA is:$$x^{\lambda(n)} = 1 \pmod n$$where \lambda is the Carmichael function. In the case of two-prime RSA it's \operatorname{lcm} (p - 1, q-1).$$m^{k \cdot \lambda(n)+1} = m \pmod n$$We choose$d$such that$e\cdot d = 1 \pmod {\lambda(n)}$. If$\operatorname{GCD}(e,\lambda(n)) = 1$then there is exactly one solution ... 1 No, RSA encryption does not provide authenticity, regardless of the padding. This is for the simple reason that anybody can encrypt with the public key. This is irrespective of the asymmetric algorithm used. You need to sign the data to obtain authenticity. What AEAD does do is to protect e.g. against padding oracle attacks. These can be performed on CBC ... 4 We have$y^2-1 \equiv 0 \pmod n$, meaning that$y^2-1 = (y+1)(y-1)$is a multiple of$n$.$y \not \equiv \pm 1 \pmod n$means that neither of$y+1$and$y-1$is a multiple of$n$. Now, clearly$\gcd(y-1,n)$is a divisor of$n$; we want to show that it is not$1$or$n$. It cannot be$1$, because that would imply that$n$divides$y+1\$, which we assume is ...