Affine cipher with non relatively prime coefficient
$begingroup$
The Affine Cipher is to encrypt a message $P$ to a cipher $C$ based on the following rule:
$$Cequiv aP + b pmod {26}, quad gcd(a,M) = 1$$
Where the message is a combination of English alphabet.
The restriction $gcd(a,M)$ is required to make the deciphering process achievable. If this restriction does not hold, the deciphering process will fail. Moreover, the enciphering process is not unique such that two message letters will be mapped to the same cipher letter.
Now, my inquiry is that, if $gcd(a,M) > 1$, what is the cipher letter such that two message letters will map to?
My try:
My thoughts is to divide both the modulus $M$ and $a$ by the $gcd(a,M)$. Then, the letter is $C - b$ will be mapped to two letters numbered $(00, a times frac{M}{gcd(a,M)} pmod M)$. Where $A:00, B:01, C:02 cdots Z:25$. However, I cannot give a reason why. Is that true? Why?
number-theory elementary-number-theory modular-arithmetic cryptography
asked Dec 6 '18 at 18:31
Maged SaeedMaged Saeed
8821417
$endgroup$
add a comment |
$begingroup$
The Affine Cipher is to encrypt a message $P$ to a cipher $C$ based on the following rule:
$$Cequiv aP + b pmod {26}, quad gcd(a,M) = 1$$
Where the message is a combination of English alphabet.
The restriction $gcd(a,M)$ is required to make the deciphering process achievable. If this restriction does not hold, the deciphering process will fail. Moreover, the enciphering process is not unique such that two message letters will be mapped to the same cipher letter.
Now, my inquiry is that, if $gcd(a,M) > 1$, what is the cipher letter such that two message letters will map to?
My try:
My thoughts is to divide both the modulus $M$ and $a$ by the $gcd(a,M)$. Then, the letter is $C - b$ will be mapped to two letters numbered $(00, a times frac{M}{gcd(a,M)} pmod M)$. Where $A:00, B:01, C:02 cdots Z:25$. However, I cannot give a reason why. Is that true? Why?
number-theory elementary-number-theory modular-arithmetic cryptography
asked Dec 6 '18 at 18:31
Maged SaeedMaged Saeed
8821417
$endgroup$
add a comment |
$begingroup$
The Affine Cipher is to encrypt a message $P$ to a cipher $C$ based on the following rule:
$$Cequiv aP + b pmod {26}, quad gcd(a,M) = 1$$
Where the message is a combination of English alphabet.
The restriction $gcd(a,M)$ is required to make the deciphering process achievable. If this restriction does not hold, the deciphering process will fail. Moreover, the enciphering process is not unique such that two message letters will be mapped to the same cipher letter.
Now, my inquiry is that, if $gcd(a,M) > 1$, what is the cipher letter such that two message letters will map to?
My try:
My thoughts is to divide both the modulus $M$ and $a$ by the $gcd(a,M)$. Then, the letter is $C - b$ will be mapped to two letters numbered $(00, a times frac{M}{gcd(a,M)} pmod M)$. Where $A:00, B:01, C:02 cdots Z:25$. However, I cannot give a reason why. Is that true? Why?
number-theory elementary-number-theory modular-arithmetic cryptography
asked Dec 6 '18 at 18:31
Maged SaeedMaged Saeed
8821417
$endgroup$
The Affine Cipher is to encrypt a message $P$ to a cipher $C$ based on the following rule:
$$Cequiv aP + b pmod {26}, quad gcd(a,M) = 1$$
Where the message is a combination of English alphabet.
The restriction $gcd(a,M)$ is required to make the deciphering process achievable. If this restriction does not hold, the deciphering process will fail. Moreover, the enciphering process is not unique such that two message letters will be mapped to the same cipher letter.
Now, my inquiry is that, if $gcd(a,M) > 1$, what is the cipher letter such that two message letters will map to?
My try:
My thoughts is to divide both the modulus $M$ and $a$ by the $gcd(a,M)$. Then, the letter is $C - b$ will be mapped to two letters numbered $(00, a times frac{M}{gcd(a,M)} pmod M)$. Where $A:00, B:01, C:02 cdots Z:25$. However, I cannot give a reason why. Is that true? Why?
number-theory elementary-number-theory modular-arithmetic cryptography
number-theory elementary-number-theory modular-arithmetic cryptography
asked Dec 6 '18 at 18:31
Maged SaeedMaged Saeed
8821417
asked Dec 6 '18 at 18:31
Maged SaeedMaged Saeed
8821417
asked Dec 6 '18 at 18:31
Maged SaeedMaged Saeed
8821417
asked Dec 6 '18 at 18:31
Maged SaeedMaged Saeed
8821417
asked Dec 6 '18 at 18:31
Maged SaeedMaged Saeed
8821417
8821417
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Yes, your idea is essentially correct.
Let $d = gcd(a, M)$. By definition, $a$ and $M$ are both divisible by $d$, i.e. $a = rd$ and $M = sd$ for some integers $r$ and $s$.
If $d > 1$, then $0 < s < M$, and so the numbers $P = 0$ and $P' = s = frac Md$ represent distinct plaintext letters. But $$aP' = as = drs = rM equiv 0 = aP pmod M,$$ which implies that $aP' + b equiv b = aP + b pmod M$.
Of course, we can find other collisions, as well. In particular, any integer multiple of $s$ will also encrypt to the ciphertext $C = b$, since $ans + b = rnM + b equiv b pmod M$ for any integer $n$.
Also, for any integer $h$, the plaintext letters represented by $Q = h$ and $Q' = s+h$ also encrypt to the same ciphertext letter, since $$aQ + b = ah + b equiv rM + ah + b = as + ah + b = aQ' + b pmod M.$$
Of course, we can also combine these two results to show that $h$ and $ns + h$ will encrypt to the same value for any $n$ and $h$.
answered Dec 10 '18 at 16:50
Ilmari KaronenIlmari Karonen
20.1k25186
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3028866%2faffine-cipher-with-non-relatively-prime-coefficient%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Yes, your idea is essentially correct.
Let $d = gcd(a, M)$. By definition, $a$ and $M$ are both divisible by $d$, i.e. $a = rd$ and $M = sd$ for some integers $r$ and $s$.
If $d > 1$, then $0 < s < M$, and so the numbers $P = 0$ and $P' = s = frac Md$ represent distinct plaintext letters. But $$aP' = as = drs = rM equiv 0 = aP pmod M,$$ which implies that $aP' + b equiv b = aP + b pmod M$.
Of course, we can find other collisions, as well. In particular, any integer multiple of $s$ will also encrypt to the ciphertext $C = b$, since $ans + b = rnM + b equiv b pmod M$ for any integer $n$.
Also, for any integer $h$, the plaintext letters represented by $Q = h$ and $Q' = s+h$ also encrypt to the same ciphertext letter, since $$aQ + b = ah + b equiv rM + ah + b = as + ah + b = aQ' + b pmod M.$$
Of course, we can also combine these two results to show that $h$ and $ns + h$ will encrypt to the same value for any $n$ and $h$.
answered Dec 10 '18 at 16:50
Ilmari KaronenIlmari Karonen
20.1k25186
$endgroup$
add a comment |
$begingroup$
Yes, your idea is essentially correct.
Let $d = gcd(a, M)$. By definition, $a$ and $M$ are both divisible by $d$, i.e. $a = rd$ and $M = sd$ for some integers $r$ and $s$.
If $d > 1$, then $0 < s < M$, and so the numbers $P = 0$ and $P' = s = frac Md$ represent distinct plaintext letters. But $$aP' = as = drs = rM equiv 0 = aP pmod M,$$ which implies that $aP' + b equiv b = aP + b pmod M$.
Of course, we can find other collisions, as well. In particular, any integer multiple of $s$ will also encrypt to the ciphertext $C = b$, since $ans + b = rnM + b equiv b pmod M$ for any integer $n$.
Also, for any integer $h$, the plaintext letters represented by $Q = h$ and $Q' = s+h$ also encrypt to the same ciphertext letter, since $$aQ + b = ah + b equiv rM + ah + b = as + ah + b = aQ' + b pmod M.$$
Of course, we can also combine these two results to show that $h$ and $ns + h$ will encrypt to the same value for any $n$ and $h$.
answered Dec 10 '18 at 16:50
Ilmari KaronenIlmari Karonen
20.1k25186
$endgroup$
add a comment |
$begingroup$
Yes, your idea is essentially correct.
Let $d = gcd(a, M)$. By definition, $a$ and $M$ are both divisible by $d$, i.e. $a = rd$ and $M = sd$ for some integers $r$ and $s$.
If $d > 1$, then $0 < s < M$, and so the numbers $P = 0$ and $P' = s = frac Md$ represent distinct plaintext letters. But $$aP' = as = drs = rM equiv 0 = aP pmod M,$$ which implies that $aP' + b equiv b = aP + b pmod M$.
Of course, we can find other collisions, as well. In particular, any integer multiple of $s$ will also encrypt to the ciphertext $C = b$, since $ans + b = rnM + b equiv b pmod M$ for any integer $n$.
Also, for any integer $h$, the plaintext letters represented by $Q = h$ and $Q' = s+h$ also encrypt to the same ciphertext letter, since $$aQ + b = ah + b equiv rM + ah + b = as + ah + b = aQ' + b pmod M.$$
Of course, we can also combine these two results to show that $h$ and $ns + h$ will encrypt to the same value for any $n$ and $h$.
answered Dec 10 '18 at 16:50
Ilmari KaronenIlmari Karonen
20.1k25186
$endgroup$
Yes, your idea is essentially correct.
Let $d = gcd(a, M)$. By definition, $a$ and $M$ are both divisible by $d$, i.e. $a = rd$ and $M = sd$ for some integers $r$ and $s$.
If $d > 1$, then $0 < s < M$, and so the numbers $P = 0$ and $P' = s = frac Md$ represent distinct plaintext letters. But $$aP' = as = drs = rM equiv 0 = aP pmod M,$$ which implies that $aP' + b equiv b = aP + b pmod M$.
Of course, we can find other collisions, as well. In particular, any integer multiple of $s$ will also encrypt to the ciphertext $C = b$, since $ans + b = rnM + b equiv b pmod M$ for any integer $n$.
Also, for any integer $h$, the plaintext letters represented by $Q = h$ and $Q' = s+h$ also encrypt to the same ciphertext letter, since $$aQ + b = ah + b equiv rM + ah + b = as + ah + b = aQ' + b pmod M.$$
Of course, we can also combine these two results to show that $h$ and $ns + h$ will encrypt to the same value for any $n$ and $h$.
answered Dec 10 '18 at 16:50
Ilmari KaronenIlmari Karonen
20.1k25186
edited Dec 10 '18 at 17:04
answered Dec 10 '18 at 16:50
Ilmari KaronenIlmari Karonen
20.1k25186
answered Dec 10 '18 at 16:50
Ilmari KaronenIlmari Karonen
20.1k25186
answered Dec 10 '18 at 16:50
Ilmari KaronenIlmari Karonen
20.1k25186
20.1k25186
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3028866%2faffine-cipher-with-non-relatively-prime-coefficient%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
