Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older editNewer edit →
Replaced content with "<br><br>Here is more info on [http://ladyleem.hubweb.net/xe/?document_srl=53975 Single In Phoenix Arizona] review our web-page."
No edit summary
Line 1: Line 1:
{{lowercase|title=dc (Unix)}}
In [[cryptography]], a '''message authentication code''' (often '''MAC''') is a short piece of information used to [[authenticate]] a [[message]].
'''dc''' is a [[cross-platform]] [[reverse Polish notation|reverse-polish]] '''d'''esk '''c'''alculator which supports [[arbitrary-precision arithmetic]].<ref>{{man|1|dc||an arbitrary precision calculator}}</ref> It is one of the oldest [[Unix]] utilities, predating even the invention of the [[C (programming language)|C programming language]]; like other utilities of that vintage, it has a powerful set of features but an extremely terse syntax.<ref>{{cite web
|url=http://plan9.bell-labs.com/7thEdMan/vol2/dc
|title=The sources for the manual page for 7th Edition Unix dc
}}</ref><ref>{{cite web
|author=Ritchie, Dennis M.
|date=Sep. 1979
|url=http://cm.bell-labs.com/cm/cs/who/dmr/hist.html
|title=The Evolution of the Unix Timesharing System
}}</ref>
Traditionally, the more user-friendly (with its [[infix notation]]) [[bc programming language|bc]] calculator program was implemented on top of dc, although more modern implementations are related in the opposite fashion: dc uses bc's library for arithmetic.<ref>{{cite web
|url= http://directory.fsf.org/project/bc/
|title=Free Software Directory: BC
|accessdate=5 Jan 2009
}}</ref>


This article provides some examples in an attempt to give a general flavour of the language; for a complete list of commands and syntax, one should consult the [[man page]] for one's specific implementation.
A MAC [[algorithm]], sometimes called a '''keyed''' ('''cryptographic''') '''hash function''', accepts as input a [[secret key]] and an arbitrary-length message to be authenticated, and outputs a MAC (sometimes known as a ''tag'').  The MAC value protects both a message's [[data integrity]] as well as its [[Authentication|authenticity]], by allowing verifiers (who also possess the secret key) to detect any changes to the message content.


==Basic operations==
== Security ==
To multiply four and five in dc (note that most of the whitespace is optional):


  4 5 *
While MAC functions are similar to [[cryptographic hash function]]s, they possess different security requirements. To be considered secure, a MAC function must resist [[existential forgery]] under [[chosen-plaintext attack]]s. This means that even if an attacker has access to an [[oracle machine|oracle]] which possesses the secret key and generates MACs for messages of the attacker's choosing, the attacker cannot guess the MAC for other messages{{clarify|why guess when the oracle will tell the attacker the MAC? By "other messages", do we mean those with different keys?|date=May 2012}} without performing infeasible amounts of computation.
p


This translates into "push four and five onto the stack, then, with the multiplication operator, pop two elements  from the stack, multiply them and push the result back on the stack."  Then the 'p' command is used to examine (print out to the screen) the top element on the stack.
MACs differ from [[digital signature]]s as MAC values are both generated and verified using the same secret key. This implies that the sender and receiver of a message must agree on the same key before initiating communications, as is the case with [[symmetric encryption]]. For the same reason, MACs do not provide the property of [[non-repudiation]] offered by signatures specifically in the case of a network-wide shared secret key: any user who can verify a MAC is also capable of generating MACs for other messages. In contrast, a digital signature is generated using the private key of a key pair, which is [[asymmetric encryption]]. Since this private key is only accessible to its holder, a digital signature proves that a document was signed by none other than that holder. Thus, digital signatures do offer non-repudiation.


The [[arithmetic precision]] is changed with the command 'k', which sets the number of fractional digits (the number of digits following the [[radix point|point]]) to be used for arithmetic operations.  Since the default precision is zero, this sequence of commands produces '0' as a result:
== Message integrity codes ==
2 3 / p


By adjusting the precision with 'k', arbitrary number of decimal places can be produced.  This command sequence outputs '.66666'.
The term ''message integrity code (MIC)'' is frequently substituted for the term MAC, especially in communications,<ref>{{cite paper |publisher=[[IEEE-SA]] |title=IEEE 802.11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications |date=12 June 2007 |doi=10.1109/IEEESTD.2007.373646 |url=http://standards.ieee.org/getieee802/download/802.11-2007.pdf | version=(2007 revision)}}</ref> where the acronym MAC traditionally stands for [[Media Access Control]]. However, some authors<ref>[http://www.cs.cornell.edu/courses/cs513/2005fa/NL20.hashing.html Fred B Schneider, Hashes and Message Digests, Cornell University]</ref> use MIC as a distinctly different term from a MAC; in their usage of the term the MIC operation does not use secret keys. This lack of security means that any MIC intended for use gauging message integrity should be encrypted or otherwise be protected against tampering. MIC algorithms are created such that a given message will always produce the same MIC assuming the same algorithm is used to generate both.  Conversely, MAC algorithms are designed to produce matching MACs only if the same message, secret key and [[initialization vector]] are input to the same algorithm.  MICs do not use secret keys and, when taken on their own, are therefore a much less reliable gauge of message integrity than MACs. Because MACs use secret keys, they do not necessarily need to be encrypted to provide the same level of assurance.


5 k
== Implementation ==
2 3 / p


To evaluate <math>\sqrt{(12 + (-3)^4)\over11}-22</math>: ('v' computes the square root of the top of the stack and '_' is used to input a negative number):
MAC algorithms can be constructed from other cryptographic primitives, such as [[cryptographic hash function]]s (as in the case of [[HMAC]]) or from [[block cipher]] algorithms ([[OMAC (cryptography)|OMAC]], [[CBC-MAC]] and [[PMAC (cryptography)|PMAC]]). However many of the fastest MAC algorithms such as [[UMAC]] and [[VMAC]] are constructed based on [[universal hashing]].<ref>{{cite paper |url=http://www.fastcrypto.org/vmac/draft-krovetz-vmac-01.txt|title=VMAC: Message Authentication Code using Universal Hashing  |accessdate=16 March 2010 |work=CFRG Working Group |publisher=CFRG Working Group}}</ref>


12 _3 4 ^ + 11 / v 22 -
== Standards ==
p
Various standards exist that define MAC algorithms. These include:
* FIPS PUB 113 ''Computer Data Authentication'',<ref>[http://www.itl.nist.gov/fipspubs/fip113.htm FIPS PUB 113 ''Computer Data Authentication'']</ref> withdrawn in 2002,<ref>[http://www.itl.nist.gov/fipspubs/withdraw.htm Federal Information Processing Standards Publications, Withdrawn FIPS Listed by Number]</ref> defines an algorithm based on [[DES]].
* [[ISO/IEC 9797-1]] ''Mechanisms using a block cipher''<ref>[http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=30656 ISO/IEC 9797-1 ''Information technology &mdash; Security techniques &mdash; Message Authentication Codes (MACs) &mdash; Part 1: Mechanisms using a block cipher'']</ref>
* ISO/IEC 9797-2 ''Mechanisms using a dedicated hash-function''<ref>[http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=31136 ISO/IEC 9797-2 ''Information technology &mdash; Security techniques &mdash; Message Authentication Codes (MACs) &mdash; Part 2: Mechanisms using a dedicated hash-function'']</ref>


To swap the top two elements of the stack, use the 'r' command. To duplicate the top element, use the 'd' command.
ISO/IEC 9797-1 and -2 define generic models and algorithms that can be used with any block cipher or hash function, and a variety of different parameters. These models and parameters allow more specific algorithms to be defined by nominating the parameters. For example the FIPS PUB 113 algorithm is functionally equivalent to ISO/IEC 9797-1 MAC algorithm 1 with padding method 1 and a block cipher algorithm of DES.


==Input/Output==
==Example==
To read a line from [[stdin]], use the '?' command.  This will evaluate the line as if it were a ''dc'' command, and so it is necessary that it be syntactically correct and potentially be a security problem since the '!' ''dc'' command will allow arbitrary command execution.
[[Image:MAC.svg]]


As mentioned above, 'p' will print the top of the stack with a newline after it. 'n' will pop the top of the stack and output it without a trailing newline. 'f' will dump the entire stack with one entry per line.
In this example, the sender of a message runs it through a MAC algorithm to produce a MAC data tag. The message and the MAC tag are then sent to the receiver. The receiver in turn runs the message portion of the transmission through the same MAC algorithm using the same key, producing a second MAC data tag. The receiver then compares the first MAC tag received in the transmission to the second generated MAC tag. If they are identical, the receiver can safely assume that the integrity of the message was not compromised, and the message was not altered or tampered with during transmission.


''dc'' also support arbitrary input and output [[radix|radices]].  The 'i' command will pop the top of the stack and use it for the input base.  Hex digits must be in upper case to avoid collisions with ''dc'' commands and are not limited to A-F if the input radix is larger than 16.  The 'o' command does the same for the output base, but keep in mind that the input base will affect the parsing of every numeric value afterwards so it is usually advisable to set the output base first.  To read the values, the 'K', 'I' and 'O' will push the current precision, input radix and output radix on to the top of the stack.
===One-time MAC===


As an example, to convert from hex to binary:
[[Universal hashing]] and in particular [[pairwise independent]] hash functions provide a message authentication code as long as the key is used at most once (or less than <math>k</math>-times for <math>k</math>-wise independent hash functions. This can be seen as of the [[one-time pad]] for authentication.
<ref>[[Gustavus Simmons]], Authentication theory/coding theory, Proceedings of CRYPTO 84 on Advances in cryptology, p.411-431, August 1985, Santa Barbara, California, United States.</ref>


16i2o DEADBEEFp
The simplest such pairwise independent hash function is defined by the random key <math>key=(a,b)</math> and the mac tag for a message <math>m</math> is computed as <math>tag:=a*m + b\;\mathit{ mod }\;p</math>, where <math>p</math> is a prime.


outputs <tt>11011110101011011011111011101111</tt>.
==See also==
* [[Integrity check value]]
* [[UMAC]]
* [[HMAC]]
* [[CMAC]]
* [[VMAC]]
* [[Poly1305-AES]]
* [[MMH-Badger MAC]]


==Language Features==
==External links==
===Registers===
* [http://www.rsasecurity.com/rsalabs/node.asp?id=2177 RSA Laboratories entry on MACs]
In addition to these basic arithmetic and stack operations, dc includes support for [[Macro (computer science)|macros]], conditionals and storing of results for later retrieval.
* [http://web.mit.edu/6.857/OldStuff/Fall97/lectures/lecture3.pdf Ron Rivest lecture on MACs]
 
The mechanism underlying macros and conditionals is the '''register''', which in dc is a storage location with a single character name which can be stored to and retrieved from: 'sc' pops the top of the stack and stores it in register c, and 'lc' pushes the value of register c onto the stack. For example:
 
3 sc 4 lc * p
 
Registers can also be treated as secondary stacks, so values can be pushed and popped between them and the main stack using the 'S' and 'L' commands.
 
===Strings===
String values are enclosed in '[' and ']' characters and may be pushed on the stack and stored in registers.  The 'a' command will convert a the low order byte of the numeric value into an [[ASCII#ASCII_printable_characters|ASCII]] character, or if the top of the stack is a string it will replace it with the first character of the string.  There are no ways to build up strings or perform string manipulation other than executing it with the 'x' command, or printing it with the 'P' command.
 
The '#' character begins a comment to the end of the line.
 
===Macros===
Macros are then implemented by allowing registers and stack entries to be strings as well as numbers. A string can be printed, but it can also be executed (i.e. processed as a sequence of dc commands). So for instance we can store a macro to add one and then multiply by 2 into register m:
 
[1 + 2 *] sm
 
and then (using the 'x' command which executes the top of the stack) we can use it like this:
 
3 lm x p
 
===Conditionals===
Finally, we can use this macro mechanism to provide conditionals. The command '=r' will pop two values from the stack, and execute the macro stored in register 'r' only if they are equal. So this will print the string 'equal' only if the top of the stack is equal to 5:
<pre>
[[equal]p] sm 5 =m
</pre>
 
Other conditionals are '>', '!>', '<', '!<', '!=', which will execute the specified macro if the top two values on the stack are greater, less than or equal to ("not greater"), less than,  greater than or equal to ("not less than"), and not equals, respectively.
 
===Loops===
Looping is then possible by defining a macro which (conditionally) reinvokes itself.  A simple factorial of the top of the stack might be implemented as:
 
# F(x): return x!
# if x-1 > 1
#    return x * F(x-1)
# otherwise
#    return x
[d1-d1<F*]dsFxp
 
The '1Q' command will exit from a macro, allowing an early return. 'q' will quit from two levels of macros (and ''dc'' itself if there are less than two levels on the call stack).  'z' will push the current stack depth before the 'z' operation.
 
==Examples==
As an example of a relatively simple program in dc, this command (in 1 line):
 
dc -e <nowiki>'[[Enter a number (metres), or 0 to exit]psj]sh[q]sz[lhx?d0=z10k39.370079*.5+0k12~1/rn[ feet ]
Pn[ inches]P10Pdx]dx'</nowiki>
 
will convert distances from metres to feet and inches; the bulk of it is concerned with prompting for input, printing output in a suitable format and looping round to convert another number.
 
As an example, here is an implementation of the [[Euclidean algorithm]] to find the [[Greatest common divisor|GCD]]:
 
dc -e <nowiki>'??[dSarLa%d0<a]dsax+p' # shortest
dc -e '[a=]P?[b=]P?[dSarLa%d0<a]dsax+[GCD:]Pp' # easier-to-read version</nowiki>
 
Computing the [[factorial]] of an input value, <math>n! = \prod_{i=1}^n i</math>
<pre>
dc -e '?[q]sQ[d1=Qd1-lFx*]dsFxp'
</pre>
 
A more complex example performs [[Diffie-Hellman key exchange]].  This was popular as a [[signature block]] among [[cypherpunk]]s during the [[ITAR]] debates<ref>{{cite web
|url=http://www.cypherspace.org/adam/rsa/perl-dh.html
|title=Diffie-Hellman in 2 lines of Perl
|accessdate=5 Jan 2009
|author=Adam Back
}}</ref>:
<pre>
#!/usr/bin/perl -- -export-a-crypto-system-sig Diffie-Hellman-2-lines
($g,$e,$m)=@ARGV,$m||die"$0 gen exp mod\n";print`echo "16dio1[d2%Sa2/d0<X+d
*La1=z\U$m%0]SX$e"[$g*]\EszlXx+p|dc`
</pre>
 
A commented version is slightly easier to understand and shows how to use loops, conditionals, and the 'q' command to return from a macro. With a modern version of dc, the '|' command can be used to do arbitrary precision modular exponentiation without needing to write the X function.
<source lang=perl>
#!/usr/bin/perl
 
my ($g,$e,$m) = map { "\U$_" } @ARGV;
die "$0 gen exp mod\n" unless $m;
 
print `echo $g $e $m | dc -e '
# Hex input and output
16dio
# Read m, e and g from stdin on one line
?SmSeSg
 
# Function z: return g * top of stack
[lg*]sz
 
# Function Q: remove the top of the stack and return 1
[sb1q]sQ
 
# Function X(e): recursively compute g^e % m
# It is the same as Sm^Lm%, but handles arbitrarily large exponents.
# Stack at entry: e
# Stack at exit: g^e % m
# Since e may be very large, this uses the property that g^e % m ==
# if( e == 0 )
# return 1
# x = (g^(e/2)) ^ 2
# if( e % 2 == 1 )
# x *= g
# return x %
[
d 0=Q # return 1 if e==0 (otherwise, stack: e)
d 2% Sa # Store e%2 in a (stack: e)
2/ # compute e/2
lXx # call X(e/2)
d* # compute X(e/2)^2
La1=z # multiply by g if e%2==1
lm % # compute (g^e) % m
] SX
 
le # Load e from the register
lXx # compute g^e % m
p # Print the result
'`;
</source>
 
== See also ==
* [[bc programming language]]
* [[Calculator input methods]]
* [[HP calculators]]
* [[Orpie]], an RPN calculator
* [[Stack machine]]


==References==
==References==
{{reflist}}
<references/>
 
==External links==
*Package [http://packages.debian.org/search?keywords=dc&searchon=names&exact=1&suite=all&section=all dc] in [[Debian GNU/Linux]] repositories
*[http://gnuwin32.sourceforge.net/packages/bc.htm Native Windows port] of ''[[bc programming language|bc]]'', which includes ''dc''.


{{unix commands}}
{{Cryptography navbox | hash}}


[[Category:cross-platform software]]
[[Category:Message authentication codes]]
[[Category:Unix software]]
[[Category:free mathematics software]]
[[Category:Numerical programming languages]]
[[Category:stack-oriented programming languages]]


[[cs:Dc (programovací jazyk)]]
[[ca:Message authentication code]]
[[de:Dc (Unix)]]
[[cs:MAC funkce]]
[[fr:Dc (logiciel)]]
[[da:Message authentication code]]
[[pl:Dc (informatyka)]]
[[de:Message Authentication Code]]
[[ru:Dc]]
[[es:Message authentication code]]
[[es:DC (Unix)]]
[[fa:کد اصالت‌سنجی پیام]]
[[fr:Code d'authentification de message]]
[[ko:메시지 인증 코드]]
[[it:Message authentication code]]
[[he:קוד אימות מסרים]]
[[ja:メッセージ認証符号]]
[[pl:Kod uwierzytelniania wiadomości]]
[[pt:Autenticador de mensagem]]
[[ru:Имитовставка]]
[[tr:Mesaj Doğrulama Kodu]]
[[uk:MAC підпис]]

Revision as of 09:21, 12 August 2014

In cryptography, a message authentication code (often MAC) is a short piece of information used to authenticate a message.

A MAC algorithm, sometimes called a keyed (cryptographic) hash function, accepts as input a secret key and an arbitrary-length message to be authenticated, and outputs a MAC (sometimes known as a tag). The MAC value protects both a message's data integrity as well as its authenticity, by allowing verifiers (who also possess the secret key) to detect any changes to the message content.

Security

While MAC functions are similar to cryptographic hash functions, they possess different security requirements. To be considered secure, a MAC function must resist existential forgery under chosen-plaintext attacks. This means that even if an attacker has access to an oracle which possesses the secret key and generates MACs for messages of the attacker's choosing, the attacker cannot guess the MAC for other messagesTemplate:Clarify without performing infeasible amounts of computation.

MACs differ from digital signatures as MAC values are both generated and verified using the same secret key. This implies that the sender and receiver of a message must agree on the same key before initiating communications, as is the case with symmetric encryption. For the same reason, MACs do not provide the property of non-repudiation offered by signatures specifically in the case of a network-wide shared secret key: any user who can verify a MAC is also capable of generating MACs for other messages. In contrast, a digital signature is generated using the private key of a key pair, which is asymmetric encryption. Since this private key is only accessible to its holder, a digital signature proves that a document was signed by none other than that holder. Thus, digital signatures do offer non-repudiation.

Message integrity codes

The term message integrity code (MIC) is frequently substituted for the term MAC, especially in communications,[1] where the acronym MAC traditionally stands for Media Access Control. However, some authors[2] use MIC as a distinctly different term from a MAC; in their usage of the term the MIC operation does not use secret keys. This lack of security means that any MIC intended for use gauging message integrity should be encrypted or otherwise be protected against tampering. MIC algorithms are created such that a given message will always produce the same MIC assuming the same algorithm is used to generate both. Conversely, MAC algorithms are designed to produce matching MACs only if the same message, secret key and initialization vector are input to the same algorithm. MICs do not use secret keys and, when taken on their own, are therefore a much less reliable gauge of message integrity than MACs. Because MACs use secret keys, they do not necessarily need to be encrypted to provide the same level of assurance.

Implementation

MAC algorithms can be constructed from other cryptographic primitives, such as cryptographic hash functions (as in the case of HMAC) or from block cipher algorithms (OMAC, CBC-MAC and PMAC). However many of the fastest MAC algorithms such as UMAC and VMAC are constructed based on universal hashing.[3]

Standards

Various standards exist that define MAC algorithms. These include:

  • FIPS PUB 113 Computer Data Authentication,[4] withdrawn in 2002,[5] defines an algorithm based on DES.
  • ISO/IEC 9797-1 Mechanisms using a block cipher[6]
  • ISO/IEC 9797-2 Mechanisms using a dedicated hash-function[7]

ISO/IEC 9797-1 and -2 define generic models and algorithms that can be used with any block cipher or hash function, and a variety of different parameters. These models and parameters allow more specific algorithms to be defined by nominating the parameters. For example the FIPS PUB 113 algorithm is functionally equivalent to ISO/IEC 9797-1 MAC algorithm 1 with padding method 1 and a block cipher algorithm of DES.

Example

In this example, the sender of a message runs it through a MAC algorithm to produce a MAC data tag. The message and the MAC tag are then sent to the receiver. The receiver in turn runs the message portion of the transmission through the same MAC algorithm using the same key, producing a second MAC data tag. The receiver then compares the first MAC tag received in the transmission to the second generated MAC tag. If they are identical, the receiver can safely assume that the integrity of the message was not compromised, and the message was not altered or tampered with during transmission.

One-time MAC

Universal hashing and in particular pairwise independent hash functions provide a message authentication code as long as the key is used at most once (or less than -times for -wise independent hash functions. This can be seen as of the one-time pad for authentication. [8]

The simplest such pairwise independent hash function is defined by the random key and the mac tag for a message is computed as , where is a prime.

See also

External links

References

  1. ↑ Template:Cite paper
  2. ↑ Fred B Schneider, Hashes and Message Digests, Cornell University
  3. ↑ Template:Cite paper
  4. ↑ FIPS PUB 113 Computer Data Authentication
  5. ↑ Federal Information Processing Standards Publications, Withdrawn FIPS Listed by Number
  6. ↑ ISO/IEC 9797-1 Information technology — Security techniques — Message Authentication Codes (MACs) — Part 1: Mechanisms using a block cipher
  7. ↑ ISO/IEC 9797-2 Information technology — Security techniques — Message Authentication Codes (MACs) — Part 2: Mechanisms using a dedicated hash-function
  8. ↑ Gustavus Simmons, Authentication theory/coding theory, Proceedings of CRYPTO 84 on Advances in cryptology, p.411-431, August 1985, Santa Barbara, California, United States.

Template:Cryptography navbox

ca:Message authentication code cs:MAC funkce da:Message authentication code de:Message Authentication Code es:Message authentication code fa:کد اصالت‌سنجی پیام fr:Code d'authentification de message ko:메시지 인증 코드 it:Message authentication code he:קוד אימות מסרים ja:メッセージ認証符号 pl:Kod uwierzytelniania wiadomości pt:Autenticador de mensagem ru:Имитовставка tr:Mesaj Doğrulama Kodu uk:MAC підпис

Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=44910"