He's faced off against Fidel Castro, Saddam Hussein, and two generations of North Korean leaders. This is not your typical boardroom negotiator. 

Bill Richardson, former governor of New Mexico, has served as U.S. Secretary of Energy and was the U.S. ambassador to the United Nations from 1997 to 1998. His new book "How to Sweet-Talk a Shark: Strategies and Stories from a Master Negotiator," was written with help from former "Daily Show" writer Kevin Bleyer.

Negotiating with thugs is a, well, specialized skill. But it's one that Richardson says has broader applications. "What I'm trying to convey is that dealing with difficult people in the international arena can also be helpful in dealing with difficult people in our daily lives, in the private sector, at home, with spouses, mothers-in-law, kids, and just in normal human transactions," Richardson told me.

I spoke with him about nature vs. nurture in creating negotiating skills, the significance of both silence and humor in conversation, and when to know it's time to close the deal with your adversary. This transcript has been edited and condensed for clarity.

Who's the toughest person you've ever negotiated with, and what was that conversation like?

The toughest negotiation I ever had was with Saddam Hussein over two Americans who were detained in Iraq, and I was able to get them out. He tried to intimidate me. He tried to get very tough, and he was physically a very large man and he would use his beady eyes and his character to try to get advantage over me. At one point in the negotiation he walked out because I insulted him by crossing my legs and inadvertently showing him the sole of my foot.

But you ended up getting the Americans out. How did you turn that around?

He walked back into the room. In the end we were able to understand each other by not insulting each other, but by trying to find common ground over the release of these two Americans. What is essential in any negotiation is you have to respect your adversary, you have to set a positive tone for the negotiations. You have to conduct the negotiations in a personal way, rather than in a strict constructionist way. You have to let the other side save face. You have to set a deadline. And you have to negotiate in good faith: Know where you want to end up.

Were you really known as the "undersecretary of thugs" in the Clinton administration?

It was a nickname that I was given, and secondly the most common description was something president Clinton once said. What he said was: "Let's send Richardson. Bad people like him."

What do you think makes you so adept at dealing with difficult people? Is it something in your unique upbringing, or is that something one can learn?

I think some of it is in my background: I was brought up in a bilingual household. My mother spoke to me in Spanish, my father in English. I was always interested in personal mediation. But what got me very interested and active in it is when I was a congressman, I used to hold town meetings in my state of New Mexico, geared toward solving problems, usually between Native Americans, Hispanics, and Anglos over issues like land, water, property, environmental issues. I would use these meetings to bring people together and I would try to mediate. And I think that's what followed me in my career. 

I think one theme that emerges in your book will likely be familiar to anyone who's done business abroad: Oftentimes there can be a lot of, well, time, before an actual negotiation takes place. Can you talk about the cultural implications of that and how to use it to one's advantage?

In negotiating internationally and overseas, it's important to know and respect the other culture. Usually international adversaries want to get to know you personally. They feel that if you're an American, you may have the upper hand. But they feel that if they have a personal connection and there's trust, it will help in making a final deal. That means time. They test you to see if you're really interested in getting to know them and actually getting to know their product--and not just making a quick appearance and a quick exit. They want to have meals with you; they want to have long meetings. They want to introduce you to their families and their staff. It's important that the first step in learning about another culture is to be absorbed in that culture and respect their tradition and their timeline.

What about when the line is crossed between "relationship-building" and stalling?

If it's obvious that they're stalling, you want to not be disrespectful, but clearly state: "Look, let's make an agreement. If it's not going to happen, it's fine, but I can't keep wasting time."

How do you know when it is time to get down to business when sometimes it's seen as a sign of weakness to make the first move?

You learn when your adversary starts also responding with humor, when you know that you've made an inroad with this person, that the stiffness you saw at first disappears. The confidence on both sides comes back. After you've been able to establish this personal connection, and that you are ready to share the credit--or profits--with your adversary. Then it's time. 

You say that humor is key to set the mood in a negotiation, but that it's also a risky move.

I think humor, you use it, but you use it selectively. You use it to make the other side feel a connection, and feel that there can be an informality and a friendship in the discussion. You don't want to use it in an insulting way, but sometimes to break a barrier.

Can you share an example? 

There've been times, dictators that have bad human-rights reputations, that I've been able to open them up by saying, "OK, so if we don't get along, you're not going to torture me, are you?" And they look at you--and then they start laughing. They know you are not serious, and you've made the atmosphere a little more conducive to conversation.

That might be a joke, but it's not an insignificant thing to say.

Don't overdo the jokes, but get in there early. You want to establish a rapport early, especially if you want to come out with a result sooner than later. 

You also in the Saddam chapter include the importance of silence and sometimes waiting it out. Is this a tactic you'd endorse?

When I say silence is important, I mean that you should not feel like you should be talking all of the time. Let the other side vent, and let the other side make their points. Sometimes, though, when you make a point and you need it to be absorbed, silence is just fine.