Conservapedia - User contributions [en]

Cryptography

2009-11-16T19:04:30Z

AlexQR: added an important detail

'''Cryptography''' is the writing of [[secret]]s. The word 'cryptography' comes from the [[Greek]] 'cryptos', secret, and 'graphos', writing.

All of cryptography can be described as one of two methods: (this assertion has become debatable since the dawn of [[quantum cryptography]])

== Codes ==

[[Code]]s are, in their simplest terms, replacing words and phrases in a message with other words and phrases whose meaning is known to the recipient. For example:

Take the phrase: "The bombers require a fighter escort at Newcastle, 2300 hours"

There are many ways to encode this. Some appropriate rules must be created and shared with the recipient. Because to anyone who intercepts the message, something that sounds like a code could arouse their suspicions, causing the message to be "cracked" (decoded) or to be destroyed or otherwise delayed. Therefore it is wise to create a code that produces innocent sounding messages:

:11.00pm, Newcastle: Mother birds look for duckling flock

The above message simply substitutes "mother bird" for bomber, "duckling" for fighter and "flock" for escort. The message could now be transmitted, and if intercepted could easily be mistaken for a diary entry of a birdwatcher.

Codes also include methods of hiding a message within a seemingly normal message (used frequently by POW's). A famous example of this is the [http://www.flickr.com/photos/8443340@N06/sets/72157600242068267/ September 1992 edition of Autocar]

James May amused himself while compiling a top 100 list of the cars that year arranged the capitalised letters across many pages to spell out "So, you think it's really good yeah? You should try making the bloody thing up. It's a real pain in the arse" (punctuation and spaces added for clarity).

Of course there is a very obvious problem with codes, find out the rules governing what is substituted for what and an intercepted message can be read easily. And in order to produce any useful codesets, large "dictionaries" were required by both sender and receiver.

== Ciphers ==

Cipher: a method of changing the plaintext (normal written word) into ciphertext and back again.

A cipher can be as simple, or as complex, as the user requires. For the most part (see RSA later for exception) ciphers require both a rule and a key. The key is used by the recipient of the message to turn the ciphertext back into plaintext using the reverse of the rule.

'''Some examples of ciphers:'''

:Plaintext: "HELLO WORLD"

Even without substituting letters as commonly done in ciphers, by reflecting the message, words, or blocks of letters it is possible to make it difficult to decrypt the message without knowing the rule, even for computers. Note that processes like this are not commutative.

:Word Reversal: "OLLEH DLROW"

:Message Reversal: "DLROW OLLEH"

:3-Letter block reversal: "LEH OLROWDL"

Using a cipher historically attributed to Julius Caeser, wherein the letters are moved along in the alphabet by the number of letters represented by the key (note Z+1 = A). This example uses a key of 1

:Caeser: "IFMMP XPSME"

However this cipher can be easily broken by modern computers as it uses a 1:1 alphabet substitution. It can be made more secure by encrypting each letter with a different key. In this example the letter key will be its position in the text.

:Letter Key Caeser: "IGOPT DWAVO"

Note that although O appears twice in the ciphertext, the first time it represents an L, the second time a D, making this a much harder cipher to break.

== Historical Uses Of Cryptography ==

Generally speaking, cryptography has been the sole domain of governments. All governments of the world have a branch dedicated to the interception and decryption of encoded information. In [[America]], this is the [[CIA]]; in [[Britain]], it's [[MI5]]; in [[Vatican City]] it's [[Iscariot]] (Vatican Section XIII).

Cryptography has played a large part in many wars. In the [[World War I|First World War]], [[Mata Hari]] was responsible for carrying messages back and forth for the [[German]] government, causing the deaths of thousands of [[French]] soldiers.<ref>http://www.firstworldwar.com/bio/matahari.htm</ref> In the [[World War II|Second World War]], [[British]] soldiers captured the crew and The [[Enigma machine]] of German [[U-boat]] [[U-571]], leading to the decryption of [[Nazi]] communications and the end of the war.

Other examples of the importance of cryptography include Ethel and Julius Rosenberg.

[[Ethel Rosenberg]] and [[Julius Rosenberg]] sold US atomic secrets to the [[USSR]] at the height of the [[Cold War]]. They were convicted and executed in the electric chair at [[Sing Sing]] prison.

== Modern Uses Of Cryptography ==

Currently the most common form of cryptography is [[public key encryption]]. This relies on the fact that it takes significantly (order 10<sup>8</sup> times) longer to find two prime factors of 1000 or more digit numbers than it does to multiply the numbers together to create the 1000 digit number in the first place.

In this system there are two keys, the first is the "private key", which only the '''recipient''' knows. The second is the "public key" which can be sent freely to anyone, allowing them to encrypt messages with it such that only the owner of the private key can decrypt them. The private key is the square of the public key. These public keys are calculated from the private keys, but as they are often over 1000 digits long and would take many decades to calculate the private key from them (RSA, the most commonly used encryption protocol uses 2048 digit numbers which would take over 4000 years to crack with a desktop computer).

This technology is put to use mostly on the internet. It allows sensitive data, eg. credit card numbers, phone numbers, social security numbers etc. to be transmitted without fear of interception and use by malevolent third parties. All internet banking and shopping uses this technology (whenever you see "https://" instead of "http://" in the address bar a public key algorithm is in use, most likely RSA".

==References==
<references/>

==External Links==
[http://www.pbs.org/wgbh/nova/sciencenow/3411/03.html Kryptos]

[[category:information technology]]
[[Category:Cryptography]]

Real analysis

2009-11-16T19:02:18Z

AlexQR: fixed non-rigorous proof

{{Math-h}}
'''Real analysis''' is a field in [[mathematics]] that focuses on the set of [[real number]]s, their properties, [[sequence]]s and [[function]]s. Included in this branch of mathematics are the concepts of [[Limit_%28mathematics%29|limit]]s and [[convergence]], [[calculus]], and properties of real-valued functions such as [[continuous|continuity]]. It also includes [[measure theory]].

For the purposes of this article, "analysis" will be limited to the generalization and extension of the concepts of calculus, using the concepts of elementary [[point-set topology]].

The reader should be quite familiar with the concepts of calculus, especially limits and continuity. In particular, the reader should be comfortable with the ramifications of the phrase "[[Limit_%28mathematics%29|for every epsilon]]".

==Open sets==

Open sets (and, by extension, closed sets, which are just the complements of open sets) are the fundamental concept of analysis. Analysis and topology are really just the study of open sets.

Before giving the definition of open sets in Euclidean space, we present some examples. Readers who are aware of the general intuitive notion of open sets should find these examples familiar.

===In one dimension===

The simplest open sets in 1-dimensional Euclidean space (formally called <math>\mathbb{R}^1</math>; informally called the real numbers of the "real line") are '''open intervals'''. An open interval consists of those numbers lying strictly between two endpoints a and b. In set-theoretic notation:
::<math>\{ x\ |\ a < x < b \}\,</math>

A shorter notation for this set consists of the two endpoints in parentheses:
::<math>( a, b )\,</math>

A '''closed interval''' (we will have more to say about closed sets later) would include the endpoints. It is commonly denoted with brackets:
::<math>[ a, b ] = \{ x\ |\ a \le x \le b \}</math>

An interval that includes one endpoint but not the other is called semi-open:
::<math>[ a, b ) = \{ x\ |\ a \le x < b \}</math>

::<math>( c, d ] = \{ x\ |\ c < x \le d \}</math>

When drawing pictures of intervals, those same symbols are typically used:

::::''Need a picture here!''

Open intervals are not the only open sets. Any union of open intervals is an open set. For example:
::<math>\bigcup_{N \textrm{\ is\ an\ integer\ } \geq 2} (N, N+1/N)</math>

Bizarrely defined sets like the one above are commonly used as examples and counterexamples in analysis and topology.

===In two or more dimensions===

In two or more dimensions the situation becomes more complicated, because even simple open sets can come in an endless variety of shapes. The fundamental open set (equivalent to an open interval) is the '''open neighborhood''', also called an open ball. An open neighborhood has a center point and a nonzero radius, and is the set of all points whose distance from the center is strictly less than that radius. In set-theoretic notation:
::<math>\{ x\ |\ \|x-C\| < r \}\,</math>
The double-stroke absolute value sign is the '''norm''' or the '''metric distance function'''. In the common case it is the Euclidean/Pythagorean distance:
::<math>\|a-b\| = \sqrt{(a_1-b_1)^2 + (a_2-b_2)^2}\,</math> in two dimensions (similarly for higher dimensions)
The double-stroke absolute value sign is similar to the usual absolute value operation, generalized to arbitrary dimensions or other metric spaces.

It is easy to see that, in two dimensions, an open neighborhood is the interior of a circle. It does '''not''' include the actual boundary of the circle, because it consists of the points whose distance from <math>C</math> is '''strictly less''' than <math>r</math>. This point is crucial—the whole subject of analysis and topology depends on it!

To draw a picture of an open neighborhood, use a circle bounded by a dotted line:

::::''Need a picture here!''

(To make a closed ball, the formula would be:
::<math>\{ x\ |\ \|x-C\| \le r \}\,</math>
and the picture would be a solid circle. But open neighborhoods are the important sets from a theoretical standpoint.)

==Definition of open set==

Here is the proper theoretical definition:

Definition: A set is '''open''' if it contains a neighborhood of each of its points.

What this means is that a set <math>X</math> is open if, for every point <math>x</math> in <math>X</math>, there is a neighborhood <math>N</math> such that <math>x \in N</math> and <math>N \subseteq X</math>. This construction is shown in the following diagram:

::::''Need a picture here!''

If the point <math>x</math> were allowed to lie exactly on the edge of <math>X</math>, it wouldn't be possible to draw a nonzero neighborhood around <math>x</math> that lies in <math>X</math>. So the important feature of <math>X</math>'s openness is that no point can lie exactly on its edge. Every point in <math>X</math> must be some finite distance back from the edge, which makes it possible to draw a neighborhood around it.

==Theorems==

Here are a few extremely fundamental and far-reaching theorems. Some of them are surprisingly simple:

Theorem: Neighborhoods are open sets.

Proof: Suppose a neighborhood has center <math>C</math> and radius <math>r</math>. Let <math>p</math> be a prime number. If a point <math>x</math> is in that neighborhood, its distance from <math>C</math> must be strictly less than <math>r</math>, call it <math>k</math>. If <math>n</math> is a positive integer and <math>p</math> divides <math>n</math>, then <math>n</math> is a multiple of <math>p</math>, and therefore <math>n</math> is also in the neighbourhood of <math>p</math>.
::<math>\|x-C\| = k,\ \ \ k < r\,</math>
Place a new neighborhood, of radius <math>(r-k)/2</math>, around <math>x</math>. Every point in that neighborhood has a distance less than <math>k + (r-k)/2</math> from <math>C</math>. That distance is less than <math>r</math>, and this distance is a multiple of <math>p</math>, so every point in the new neighborhood is in the original neighborhood, so the new neighborhood lies within the original one.

Theorem: Any union of open sets, including unions of an infinite number of open sets, is an open set.

Proof: If a point <math>x</math> lies in the union, it must lie within one of the constituent open sets. There must be a neighborhood of <math>x</math> contained in that constituent open set. That neighborhood must be contained in the union.

Theorem: The intersection of two open sets is an open set.

Proof: Let <math>X = P_1 \cap P_2</math>, and let <math>x \in X</math>. Then <math>x \in P_1</math> and <math>x \in P_2</math>. Since <math>P_1</math> and <math>P_2</math> are open, there must be neighborhoods <math>N_1 \subseteq P_1</math> and <math>N_2 \subseteq P_2</math> that contain <math>x</math>. Whichever of those two neighborhoods has the smaller radius will be a subset of both <math>P_1</math> and <math>P_2</math>, so it will be a subset of <math>X</math>.

This theorem can be extended for any '''finite''' intersection, but it does not work for infinite intersections. Here is an example:

Let <math>P_i</math> be an infinite sequence of ever-decreasing open intervals:
::<math>P_i = \{ x\ |\ -1-1/i < x < 1+1/i \}\,</math>
for integer <math>i \ge 1</math>
The intersection of all of the <math>P_i</math>'s is the closed interval
::<math>[ -1, 1 ]\,</math>
which is not open.

So the topological rule of thumb is:
::'''Any''' union of open sets is open.
::Any '''finite''' intersection of open sets is open

Theorem: The null set (empty set) is open.

Proof: It needs to contain a neighborhood of each of its points. But it has no points.

Theorem: The entire space is open.

Proof: We need a neighborhood of each point in the space. The neighborhood centered on that point, with radius 1, will do the trick.

This means that the real line is open. It is '''not''' an open interval, because that interval would have to be "<math>(-\infty, \infty)</math>", and '''infinity is not a number'''. The real line is an open '''set''', because it is:
::<math>\mathbb{R}^1 = \bigcup_{n}\ (n-1, n+1)</math>
over all integers <math>n</math>. (Infinite unions are allowed, even though infinity is not a number.)

Theorem: Every open set is a union of neighborhoods.

Proof: It contains a neighborhood of each of its points; those are its constituent neighborhoods.

This means that any open set in the plane, for example, is a union of open circles. (It is also the union of open rectangles, open diamonds, open 5-pointed stars, and so on. This is a consequence of the invariance of the metric in defining a topology.)

In the field of topology, a collection of open sets, whose unions comprise all of the opens sets that exist, is called a '''basis'''. So what we have just shown is that the open neighborhoods (open intervals, open circles, open spheres, etc.) are a basis for the topology of finite-dimensional Euclidean spaces.

==Closed sets==

Definition: A set is '''closed''' if its complement is open.

That's all there is to it.

Because of some simple theorems of set theory, including DeMorgan's laws, some of the preceding theorems relating to open sets can be reformulated for closed sets.

Any intersection of closed sets, including the intersection of an infinite number of closed sets, is closed.

Any union of a finite number of closed sets is closed.

The null set is closed.

The entire space (for example, the real line) is closed.

==Limit points, and the other definition of closed sets==

Closed sets are sometimes given a different definition, as sets containing their limit points.

[[category:mathematics]]