cipher.in

第四届百度杯预赛解题报告 武汉大学20090315

135
Cipher
Description
The Playfair cipher or
Playfair square
is a manual symmetric encryption technique and was the first literal digraph
substitution cipher
The technique encrypts pairs of letters digraphs instead of single letters as in the 
simple substitution cipher
and rather more complex Vigenere cipher systems then in use
The Playfair is thus significantly harder to break
since the frequency analysis
used for simple substitution ciphers does not work with it
Frequency analysis can still be undertaken but on the all possible digraphs
rather
than the twenty six possible monographs
The frequency analysis of digraphs is possible
but considerably more difficult
and it generally requires a much larger ciphertext in order to be useful
Despite its invention by Wheatstone
it became known as the Playfair cipher after Lord Playfair
who heavily promoted its use
The first recorded description of the Playfair cipher was in a document
signed by Wheatstone on March
It was used for tactical purposes
by British forces in the Second Boer War and
in World War I and for the same purpose by the Australians and Germans
during World War II
This was because Playfair is reasonably
fast to use and requires no special equipment
A typical scenario for Playfair use
would be to protect important but non critical secrets during actual combat
By the time the enemy cryptanalysts could break the message
the information was useless to them
However Playfair is no longer used by military forces
because of the advent of digital encryption devices
Playfair is now regarded as
insecure for any purpose because
modern handheld computers could easily break the cipher within seconds
The Playfair cipher uses a five by five table containing a keyword or phrase
Memorization of the keyword
and four simple rules
was all that was required to create the five by five table
and use the cipher
To generate the key table
one would first fill
in the spaces in the table with
the letters of the keyword
dropping any duplicate letters
then fill the remaining spaces
with
the rest of the letters of the alphabet in order
usually omitting Q to reduce the alphabet to fit
The key can be written in the top rows of the table
from left to right
or in some other pattern
such as a spiral beginning in the upper
left
hand corner and ending in the center
The keyword together with
the conventions for filling
in the five by five table constitute the cipher key
To encrypt a message
one would change the lowercase to uppercase
break the message into digraphs groups of two letters and throw away spaces
such that
for example
Hello World becomes HE LL OW OR LD
and map them out on the key table
The two letters of the digraph
look like the corners of a rectangle in the key table
Note the relative position of the corners of this rectangle
Then apply the following four rules
in order
to each pair of letters in the plaintext
If both letters are the same
or only one letter is left
add an X after the first letter
Encrypt the new pair and continue
If the letters appear on the same row of your table
replace them with the letters to their immediate right respectively
wrapping around to the left side of
the row if a letter
in the original pair was on the right side of the row
If the letters appear on the same column of your table
replace them
with the letters immediately
below respectively wrapping around
to the top side of the column if a letter
in the original pair was on the bottom side of
the column
If the letters are not on the same row or column
replace them with the letters
on the same row
respectively but at the other pair of
corners of the rectangle defined by the original pair
The order is important
the first encrypted letter of the pair
is the one that lies on the same row as the first plaintext letter
If only one character in last group append a dummy character X at the end
Input
The input consists of multiple test cases
Each test case containing two lines the key and the message
Output
For each test case print one
line containing the encrypted message
Playfair over
I am happy to join with you today
in what will go down
in history
as the greatest demonstration for freedom in the history of our nation
Five score years ago
a great American
in whose symbolic shadow we stand today
signed the Emancipation Proclamation
This momentous decree came as a great beacon light of hope
to millions of Negro slaves who had been seared in the flames of withering injustice
It came as a joyous daybreak to end the long night of their captivity
But one hundred years later
the Negro still is not free
One hundred years later
the life of the Negro is still sadly crippled by the manacles of segregation and the chains of discrimination
One hundred years later
the Negro lives on a lonely island of poverty in the midst of a vast ocean of material prosperity
One hundred years later
the Negro is still languished in the corners of American society and finds himself an exile in his own land
And so we have come here today to dramatize a shameful condition
In a sense we have come to our nation capital to cash a check
When the architects of our republic wrote the magnificent words of the Constitution
and the Declaration of Independence
they were signing a promissory note to which every American was to fall heir
This note was a promise that all men
yes
black men as well as white men
would be guaranteed the unalienable Rights of Life Liberty and the pursuit of Happiness
It is obvious today that America has defaulted on this promissory note
insofar as her citizens of color are concerned
Instead of honoring this sacred obligation
America has given the Negro people a bad check
a check which has come back marked insufficient funds
But we refuse to believe that the bank of justice is bankrupt
We refuse to believe that there are insufficient funds in the great vaults of opportunity of this nation
And so
we have come to cash this check
a check that will give us upon demand the riches of freedom and the security of justice
We have also come to this hallowed spot to remind America of the fierce urgency of Now
This is no time to engage in the luxury of cooling off or to take the tranquilizing drug of gradualism
Now is the time to make real the promises of democracy
Now is the time to rise from the dark and desolate valley of segregation to the sunlit path of racial justice
Now is the time to lift our nation from the quicksands of racial injustice to the solid rock of brotherhood
Now is the time to make justice a reality for all of God children
It would be fatal for the nation to overlook the urgency of the moment
This sweltering summer of the Negro legitimate discontent will not pass until there is an invigorating autumn of freedom and equality
Nineteen sixty three is not an end
but a beginning
And those who hope that the Negro needed to blow off steam and will now be content will have a rude awakening if the nation returns to business as usual
And there will be neither rest nor tranquility in America until the Negro is granted his citizenship rights
The whirlwinds of revolt will continue to shake the foundations of our nation until the bright day of justice emerges
But there is something that I must say to my people
who stand on the warm threshold which leads into the palace of justice
In the process of gaining our rightful place
we must not be guilty of wrongful deeds
Let us not seek to satisfy our thirst for freedom by drinking from the cup of bitterness and hatred
We must forever conduct our struggle on the high plane of dignity and discipline
We must not allow our creative protest to degenerate into physical violence
Again and again
we must rise to the majestic heights of meeting physical force with soul force
The marvelous new militancy which has engulfed the Negro community must not lead us to a distrust of all white people
for many of our white brothers
as evidenced by their presence here today
have come to realize that their destiny is tied up with our destiny
And they have come to realize that their freedom is inextricably bound to our freedom 
We cannot walk alone
And as we walk
we must make the pledge that we shall always march ahead
We cannot turn back
There are those who are asking the devotees of civil rights
When will you be satisfied
We can never be satisfied as long as the Negro is the victim of the unspeakable horrors of police brutality
We can never be satisfied as long as our bodies
heavy with the fatigue of travel
cannot gain lodging in the motels of the highways and the hotels of the cities
We cannot be satisfied as long as the negro basic mobility is from a smaller ghetto to a larger one
We can never be satisfied as long as our children are stripped of their self hood and robbed of their dignity by signs stating
For Whites Only
We cannot be satisfied as long as a Negro in Mississippi cannot vote and a Negro in New York believes he has nothing for which to vote
No
no
we are not satisfied
and we will not be satisfied until
justice rolls down like waters and righteousness like a mighty stream
I am not unmindful that some of you have come here out of great trials and tribulations
Some of you have come fresh from narrow jail cells
And some of you have come from areas where your quest
quest for freedom left you battered by the storms of persecution and staggered by the winds of police brutality
You have been the veterans of creative suffering
Continue to work with the faith that unearned suffering is redemptive
Go back to Mississippi
go back to Alabama
go back to South Carolina
go back to Georgia
go back to Louisiana
go back to the slums and ghettos of our northern cities
knowing that somehow this situation can and will be changed
Let us not wallow in the valley of despair
I say to you today
my friends
And so even though we face the difficulties of today and tomorrow
I still have a dream
It is a dream deeply rooted in the American dream
I have a dream that one day this nation will rise up and live out the true meaning of its creed
We hold these truths to be self evident that all men are created equal
I have a dream that one day on the red hills of Georgia
the sons of former slaves and the sons of former slave owners will be able to sit down together at the table of brotherhood
I have a dream that one day even the state of Mississippi
a state sweltering with the heat of injustice
sweltering with the heat of oppression
will be transformed into an oasis of freedom and justice
I have a dream that my four little children will one day live in a nation where they will not be judged by the color of their skin but by the content of their character 
I have a dream today
I have a dream that one day
down in Alabama
with its vicious racists
with its governor having his lips dripping with the words of interposition and nullification
one day right there in Alabama little black boys and black girls will be able to join hands with little white boys and white girls as sisters and brothers
I have a dream today
I have a dream that one day every valley shall be exalted
and every hill and mountain shall be made low
the rough places will be made plain
and the crooked places will be made straight
and the glory of the Lord shall be revealed and all flesh shall see it together
This is our hope
and this is the faith that I go back to the South with
With this faith
we will be able to hew out of the mountain of despair a stone of hope
With this faith
we will be able to transform the jangling discords of our nation into a beautiful symphony of brotherhood
With this faith
we will be able to work together
to pray together
to struggle together
to go to jail together
to stand up for freedom together
knowing that we will be free one day
And this will be the day this will be the day when all of God children will be able to sing with new meaning
My country tis of thee sweet land of liberty of thee I sing
Land where my fathers died land of the Pilgrim pride
From every mountainside let freedom ring
And if America is to be a great nation this must become true
And so let freedom ring from the prodigious hilltops of New Hampshire
Let freedom ring from the mighty mountains of New York
Let freedom ring from the heightening Alleghenies of Pennsylvania
Let freedom ring from the snow capped Rockies of Colorado
Let freedom ring from the curvaceous slopes of California
But not only that
Let freedom ring from Stone Mountain of Georgia
Let freedom ring from Lookout Mountain of Tennessee
Let freedom ring from every hill and molehill of Mississippi
From every mountainside let freedom ring
And when this happens when we allow freedom ring
when we let it ring from every village and every hamlet
from every state and every city
we will be able to speed up that day when all of God children
black men and white men
Jews and Gentiles
Protestants and Catholics
will be able to join hands and sing in the words of the old Negro spiritual
Free at last
Free at last
Thank God Almighty we are free at last
I have a dream over